An Improved Estimation of the RSA Quantum Breaking Success Rate

The security of RSA cryptosystem is based on the assumption that factorization is a difficult problem from the number theoretic point of view. But that statement does not hold with regard to quantum computers where massive parallelization of computations leads to qualitative speedup. The Shor’s quantum factorization algorithm is one the most famous algorithms ever proposed. That algorithm has linear time complexity but is of probabilistic nature. It succeeds only when some random parameter fed at algorithm input has desired properties. It is well known that such parameters are found with probability not less than 1/2. However, the described in the paper numerical simulations prove that probability of such event exhibits grouping at some discrete levels above that limit. Thus, one may conclude that usage of the common bound leads to underestimation of the successful factorization probability. Empirical formulas on expected success probability introduced in the paper give rise to the more profound analysis of the Shor’s algorithm classic part behaviour. The observed grouping still awaits for explanations based on number theory.