publication . Preprint . 2006

Sharp probability estimates for Shor's order-finding algorithm

Bourdon, P. S.; Williams, H. T.;
Open Access English
  • Published: 21 Jul 2006
Let N be a (large positive integer, let b > 1 be an integer relatively prime to N, and let r be the order of b modulo N. Finally, let QC be a quantum computer whose input register has the size specified in Shor's original description of his order-finding algorithm. We prove that when Shor's algorithm is implemented on QC, then the probability P of obtaining a (nontrivial) divisor of r exceeds 0.7 whenever N exceeds 2^{11}-1 and r exceeds 39, and we establish that 0.7736 is an asymptotic lower bound for P. When N is not a power of an odd prime, Gerjuoy has shown that P exceeds 90 percent for N and r sufficiently large. We give easily checked conditions on N and r...
free text keywords: Quantum Physics
Related Organizations
Download from

[1] A. Ekert and R. Josza, Quantum computation and Shor's factoring algorithm, Rev. Mod. Phys. 68 (1996), 733-753.

[2] E. Gerjuoy, Shor's factoring algorithm and modern cryptography. An illustration of the capabilities inherent in quantum computers., Am. J. Phys. 73 (2005), 521-540.

[3] I. N. Herstein, Topics in Algebra, Wiley, New York, 1975.

[4] I. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer-Verlag, New York, 1990

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue