I have read a few articles and watched some Youtube videos explaining the algorithm of RSA. It seems that RSA is mainly based on a mathematical trick (Prime Factorization). I am wondering though what's the relation between both Prime Factorization and Prime numbers distribution law? and also what would be the sort of RSA if someone could figure a mathematical solution for Prime numbers distribution (e.g: unsolved Riemann hypothesis)?

  • 1
    $\begingroup$ This is answered in the answers to another question here $\endgroup$ – kodlu Aug 18 '16 at 22:44
  • $\begingroup$ Imagine the number of atoms in the universe. Then put this many prime numbers into each atom in the universe. Then the whole universe would contain (very roughly) as many primes at there are primes with $512$ bit. Any thought of iterating over prime numbers (even if you know exactly where to look) is not realistic. $\endgroup$ – tylo Aug 19 '16 at 18:12

The best factorisation algorithms are already much faster, subexponential but superpolynomial in complexity, than any improvement possible in brute force key search algorithms due to the Riemann Hypothesis, which would still be exponential in complexity.

The Riemann hypothesis would give a much better error term in the Prime Number Theorem, i.e., the distribution of the primes. This improvement, however, won't have much bearing on factoring efficiency. At the large sizes used for RSA, there are way too many prime number pairs that could have been used to obtain the RSA modulus $N.$

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.