1
$\begingroup$

Ok so I have heard in all sorts of places that Riemmans hypothesis has very important uses in cryptography. I have heard in many places that if someone solved it he would be able to hack various encryption systems and stuff like that.

My question is bipartite. In the first place. I read in wikipedia that the Riemann hypothesis states that the non trivial roots of the Riemman zeta function have real part 1/2. Could someone explain how this helps in finding primes.

In the second place: why does someone need to prove it to be able to use it? I mean, cant somebody assume its true and use it without the proof? Thank you all vary much in advance.

  • 0
    You are correct that for the purpose of using RH as a hack (whatever that would mean), you wouldn't need a proof. I am reminded of a line from Section 8.2 of Henri Cohen's 1st book on computational number theory about the difference between factorization algorithms and primality tests: "... the situation is completely different in factoring algorithms. There, we can use any kinds of unproved hypotheses or crystal balls for that matter, since once the algorithm (or pseudo-algorithm) finishes, one can check [whether we have a factor] without worrying about the manner in which it was obtained."2012-12-29

1 Answers 1

8

You have heard wrong. The Riemann hypothesis is related to the distribution of primes. Some forms of encryption rely on the difficulty of factoring large composite numbers. These are very different problems, related only in that they involve primes.

EDIT: One source of confusion is the fact that one deterministic version of the Miller-Rabin test for whether a number is prime assumes the generalized Riemann hypothesis. That is, if GRH is true the algorithm is guaranteed to give correct results. If it is false, it might say that a number is prime when it actually is not. However, this is not relevant to cryptography for several reasons:

  1. Better deterministic tests are now available that don't rely on unproven hypotheses.
  2. Even if such false positives exist, they would be extremely rare.
  3. For practical cryptographic purposes, "very probably prime" is just as good as provably prime.

It is conceivable that primality tests assuming the RH might be useful in the future. But, as you remarked, you don't have to prove the hypothesis to use it.

  • 1
    So the riemman hypothesis doesnt have important implications in cryptography?2012-12-28