Re: Riemann Hypothesis and P vs NP

From: Ashlie Benjamin Hocking (abh2n_at_cobra.cs.Virginia.EDU)
Date: 02/09/04 

Date: 09 Feb 2004 15:15:35 -0500

aviles94@rcn.com (Enrique) writes:
> A few months ago I finished reading "The Music of the Primes" by
> Marcus du Sautoy. Chapter 10 (titled Cracking Number and Codes) talks
> about cryptography with special emphasis on RSA. Somwhere in the
> chapter the author mentions P versus NP since factorising numbers is a
> difficult problem (personally, I don't know if it is NP-hard or
> NP-complete). At some point the author writes:
>
> "If the Riemann Hypothesis is true, then there is a fast way to
> discover the primes used to build the RSA codes on which the security
> of e-business currently relies."
>
> My question is: If the RH is proved to be true does it automatically
> follow that P=NP?

There seems (to me) to be a flaw in the author's argument.

Either the Riemann Hypothesis is true or it is not true.
If one were to assume that it were true, from which it automatically
follows that there is a fast way to discover the primes (from the
author's argument).

For any given number that needs to be factored, this fast way could be
used, and then the results quickly verified. If the results are
incorrect (or if it is not "fast"), and the author's assumption is
true, then the RH is false.

So, you can either crack every code fairly quickly or you can disprove
the RH. Either one sounds like a huge advance.

Perhaps the author is intimating that the proof of the RH should
reveal a fast way to discover the primes, but I don't see how this
follows.

---------------------------------------------------------------------
                          | "Good and evil both increase at compound
Ben Hocking, Grad Student | interest. That is why the little
hocking@cs.virginia.edu | decisions you and I make every day are of
                          | such infinite importance." - C. S. Lewis
---------------------------------------------------------------------

Relevant Pages

  • Re: Riemann Hypothesis and P vs NP
    ... >>discover the primes used to build the RSA codes on which the security ... > One of the steps in generating a RSA public/private keypair is choosing ... RH gives you a fast way to discover ... has used to build her RSA code. ...
    (comp.theory)
  • Re: Riemann Hypothesis and P vs NP
    ... >> about cryptography with special emphasis on RSA. ... >> discover the primes used to build the RSA codes on which the security ... certain numbers, randomly chosen, will have a well-behaved probability ...
    (comp.theory)
  • Re: Riemann Hypothesis and P vs NP
    ... > "there is a fast way to discover the primes used to build the RSA ...
    (sci.math)
  • Re: Riemann Hypothesis and P vs NP
    ... > "there is a fast way to discover the primes used to build the RSA ...
    (sci.crypt)
  • Re: Riemann Hypothesis and P vs NP
    ... > "there is a fast way to discover the primes used to build the RSA ...
    (comp.theory)
Loading