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/