Improving the Success Probability for Shor's Factoring Algorithm

2002/08/29 by Gregor Leander, Leander, Gregor · 1 citation
Computer Science · Engineering · Physics and Astronomy · #Coding theory and cryptography #Cryptography and Data Security #FOS: Physical sciences #Quantum Physics (quant-ph) #graph theory and CDMA systems #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0208183

arxiv created 2002/08/29 · openalex publication_date 2002/08/29 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given n=p*q with p and q prim and y in Z_p*q^*. Shor's Algorithm computes the order r of y, i.e. y^r=1 (mod n). If r=2k is even and y^k ≠ -1 (mod n) we can easily compute a non trivial factor of n: gcd(y^k-1,n). In the original paper it is shown that a randomly chosen y is usable for factoring with probabily 1/2. In this paper we will show an efficient possibility to improve the lower bound of this probability by selecting only special y in Z_n^* to 3/4, so we are able to reduce the fault probabilty in the worst case from 1/2 to 1/4.

Cited by

• Enhancing the Practical Reliability of Shor's Quantum Algorithm via Generalized Period Decomposition: Theory and Large-Scale Empirical Validation

Related

• Asymptotic Vanishing of the Success Probability in Shor's Algorithm
• Note on Integer Factoring Algorithms II
• A Re-evaluation of Shor's Algorithm
• Shor's Algorithm for Factoring Large Integers
• The distribution of solutions to xy = N mod a with an application to factoring integers