Geodesic
Prime witnesses in the Shor algorithm and the Miller--Rabin algorithm
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 12 (2008), pp. 43-48.

Voir la notice de l'article provenant de la source Math-Net.Ru

We prove that prime witnesses in the Miller–Rabin algorithm coincide with those in the Shor algorithm which satisfy the condition of Fermat's little theorem. We describe the set of natural numbers, whose prime witnesses in the Miller–Rabin algorithm coincide with those in the Shor algorithm. We find all such numbers less than 100000000 and experimentally study the rate of increase of the ratio of the quantity of such numbers to the quantity of Carmichael numbers.
Keywords: Shor's algorithm, Fermat's little theorem, strong pseudoprime witnesses, Carmichael numbers.
Mots-clés : Miller–Rabin algorithm 
@article{IVM_2008_12_a5,
     author = {\'E. Yu. Lerner},
     title = {Prime witnesses in the {Shor} algorithm and the {Miller--Rabin} algorithm},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {43--48},
     publisher = {mathdoc},
     number = {12},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2008_12_a5/}
}
TY  - JOUR
AU  - É. Yu. Lerner
TI  - Prime witnesses in the Shor algorithm and the Miller--Rabin algorithm
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2008
SP  - 43
EP  - 48
IS  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2008_12_a5/
LA  - ru
ID  - IVM_2008_12_a5
ER  - 
%0 Journal Article
%A É. Yu. Lerner
%T Prime witnesses in the Shor algorithm and the Miller--Rabin algorithm
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2008
%P 43-48
%N 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2008_12_a5/
%G ru
%F IVM_2008_12_a5
É. Yu. Lerner. Prime witnesses in the Shor algorithm and the Miller--Rabin algorithm. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 12 (2008), pp. 43-48. http://geodesic.mathdoc.fr/item/IVM_2008_12_a5/

[1] Shor P. W., “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM J. Comput., 26:5 (1997), 1484–1509 ; http://lanl.arxiv.org/quant-ph/9508027 | DOI | MR | Zbl | MR

[2] Kitaev A. Yu., Shen A., Vyalyi M. N., Klassicheskie i kvantovye vychisleniya, MTsNMO, M., 1999, 192 pp. | MR

[3] Koblits N., Kurs teorii chisel i kriptografii, TVP, M., 2001, 254 pp. | MR

[4] Motwani R., Raghavan P., Randomized algorithms, Cambridge Univ. Press, 1995, 380 pp. | MR | Zbl

[5] Kormen T., Leizerson Ch., Rivest R., Algoritmy: postroenie i analiz, MTsNMO, M., 1999, 960 pp. | MR

[6] Monier L., “Evaluation and comparision of two efficient probabilistic primary testing algorithm”, Theor. Comput. Sci., 1980, no. 12, 97–108 | DOI | MR | Zbl

[7] Knut D., Iskusstvo programmirovaniya. T. 2. Poluchislennye algoritmy, Vilyams, M., 2003, 832 pp. | MR

[8] Aierlend K., Rouzen M., Klassicheskoe vvedenie v sovremennuyu teoriyu chisel, Mir, M., 1987, 415 pp. | MR

[9] Littlvud Dzh., Matematicheskaya smes, Nauka, M., 1978, 144 pp. | MR

[10] Alford W. R., Graville A., Pomerance C., “There are infinitely many Carmichael numbers”, Annals Math., 1994, no. 140, 703–722 | DOI | MR | Zbl