2
$\begingroup$

I don't have the background for dealing with Riemann hypothesis but is well known that covers the prime distribution below a specified number.

In order to solve the RSA problem you have to factor the semiprime or calculate the totient itself, that's hard as factoring the modulus.

Question is, could Riemann hypothesis be used to calculate how many coprimes are below the modulus by counting the primes below $n$ and also counting how many products of those primes are below $n$, except those involving $p$ and $q$?

If the previous is negative, can someone clarify why some people say that Riemann hypothesis could "break" RSA?

Thanks for your patience and comprehension.

|improve this question
$\endgroup$
  • 5
    $\begingroup$ "In order to solve the RSA problem you have to factor the semiprime"; actually, that's not known to be true. There is no known way to compute e-th roots modulo a composite that's not equivalent to factoring the composite, but we also have no proof that there isn't such a method. $\endgroup$ – poncho Dec 3 '15 at 20:16
  • 2
    $\begingroup$ Well, we know the Riemann hyptothesis. Many people think / are willing to assume it's true for more than 100 years (IIRC). So if there'd be a way to use it for factoring somebody would have found it (I hope). AND it only can tell you about how many primes are below a bound, but it doesn't tell us candidates for the factors or othwise smallens the search space... $\endgroup$ – SEJPM♦ Dec 3 '15 at 21:58
  • $\begingroup$ @SEJPM: thanks, that's what I was looking for. Since Riemann hypothesis only give us the prime quantity below but no more information is given about the possible composition of those primes, so totient's still unknown. $\endgroup$ – kub0x Dec 4 '15 at 3:52
  • $\begingroup$ @poncho: already knew the issue about e-th roots btw, but sorry if I didn't include it, I found more important the following statement, as the Wikipedia also does: "The most efficient method known to solve the RSA problem is by first factoring the modulus N. A task believed to be impractical, if N is sufficiently large." $\endgroup$ – kub0x Dec 4 '15 at 3:59
  • $\begingroup$ People that say "Riemann hypothesis could break RSA" do not know what they are talking about. $\endgroup$ – j.p. Dec 4 '15 at 8:05
4
$\begingroup$

It's not that proving the Riemann Hypothesis would itself lead to a breakthrough against RSA. Rather, it's speculation that the methods leading to the discovery of a proof of the Riemann Hypothesis could lead to a profound discovery about prime numbers that, say, makes factoring easy.

The reason that proving the Riemann Hypothesis in itself has no bearing on RSA's security is that we can simply accept it as true now. We don't need to wait for a proof to use the Riemann Hypothesis to find holes in RSA. If we found a way to use the (apparent) fact that all nontrivial zeros of the zeta function have real part $\frac 12$ to crack RSA, and this crack actually worked, then it simply doesn't matter whether the Riemann Hypothesis was proved.

|improve this answer
$\endgroup$
3
$\begingroup$

The answer above is correct in terms of direct impact on factoring.

However, the connection between RH and factoring is a bit more than the fact that all nontrivial zeroes have real part 1/2. 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. See, for example

https://primes.utm.edu/notes/rh.html

and if you're interested in other consequences of RH, see the answers to

https://mathoverflow.net/questions/17209/consequences-of-the-riemann-hypothesis

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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