Re: Speculative, but at least interesting

From: Bob Silverman (anonymous_at_mathforum.org)
Date: 09/07/04 

Date: Tue, 7 Sep 2004 19:41:48 +0000 (UTC)

On 07 Sep 2004, Marko Amnell wrote:
>anonymous@mathforum.org (Bob Silverman) wrote:
>
>> > "if somebody really has cracked the so-called Riemann hypothesis,
>> > financial disaster might follow. Suddenly all cryptic codes could be
>> > breakable. No internet transaction would be safe."
>>
>> Let's start here. A proof of R.H. would have ZERO, repeat ZERO
>> effect on cryptography.
>
>With the proviso that my knowledge of cryptography is limited to
>an elementary discussion of RSA public-key cryptography in
>Kenneth Rosen's _Elementary Number Theory and its Applications_
>(pp. 259-271; I re-read this section recently because of the brouhaha
>over de Branges's supposed proof of the RH), I'd just like to ask
>what is the thinking behind the apparent fear among experts that
>a proof of RH would endanger internet security? Keith Devlin comments
>on this in his book _The Millennium Problems_ as follows:

Keith Devlin is a fine mathematician; probably better than me.
He is not, however, an expert on breaking public key crypto.

When you say "among experts", to which experts do you refer?
Certainly factoring experts have no such fear.

>
>"Since the Riemann hypothesis tells us so much about the primes, a
>proof of that conjecture might well lead to a major breakthrough
>in factoring techniques.

This is vacuous.

> Indeed, some factoring
>methods work on the _assumption_ that it's true.

No. Shanks has a method based upon the infrastructure of quadratic
fields whose fully proved run time is O(N^1/4). We can prove a
faster run time if RH is true, but the correctness of the method
does NOT depend on RH. I know of no factoring methods which
depend on the correctness of RH in order to work.

Rather, the fear
>among the encryption community is that the _methods_ used to prove
>the hypothesis will involve new insights into the pattern of the
>primes that will lead to better factoring method." (p. 50)

I can't imagine how. Certainly some new technique discovered while
proving RH *might* lead to a new factoring technique. But this is
pure speculation. It might also be the case that some new technique
unrelated to RH will lead to a better factoring method. The 'RH'
part is a red-herring. As far as anyone currently knows, factoring
algorithms do NOT depend on gaps between primes.

>
>This is rather vague. Can anyone explain how a proof of the RH might
>allow someone to break the RSA codes? Inquiring minds want to know...

Noone knows how this might happen.

Relevant Pages

  • Re: A very general question relating to Cryptography
    ... based on Group Theory, Finite Fields, Modular arithmetic ... But the point is that even if someday someone figures out how to efficiently factor integers, it does not imply that the theory of cryptography is in trouble because it is *not* based on factoring but rather based on OWF's and PRG's, of which factorization of integers is only one type of them. ...
    (sci.math)
  • Re: Prime Decomposition
    ... > large enough that the naieve algorithm is too slow. ... fact in the world of cryptography: ... RSA public-key cryptosystem) relies on the "impossibility" ... of factoring large numbers in a reasonable amount of time. ...
    (sci.math)
  • Prime Factors
    ... I probaby dont need to tell about importance of factoring into primes ... for cryptography, so ill just ask the question: ... Although there is no published algorithm for efficient factorization ...
    (sci.math.num-analysis)
  • Re: JSH: Necessity and discovery
    ... factoring are just secondary. ... The mathematics is correct and it guarantees finding a factor, ... slow factoring methods. ... But no matter what game plans the lawyers may come up with for the ...
    (sci.crypt)
  • Re: The factoring problem
    ... It's not a stupid question, it's a very important question indeed. ... A lot of people to talk about whether factoring in the NP complexity ... class as being important to cryptography. ... the problem at infinity. ...
    (sci.crypt)
Quantcast