Re: Riemann Hypothesis and P vs NP

From: Gareth Rees (gareth.rees_at_pobox.com)
Date: 02/12/04

  • Next message: Stephen Harris: "Re: Church-Turing compared to Zuse-Fredkin thesis (two new papers)" 
    Date: 12 Feb 2004 07:27:15 -0800

    Enrique wrote:
    > from Chapter 10 of "The Music of the Primes" by Marcus du Sautoy:
    >
    > "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."

    This sentence is true, strictly speaking, but it suggests to me that the
    author has misunderstood some aspects of this:

    We have had, for some time, fast ways to discover the primes used to
    build RSA codes. Namely, fast randomized primality testing algorithms
    such as that of Solovay and Strassen [4] or Rabin [3].

    I guess that du Sautoy is thinking of Miller's proof that if the
    Extended Riemann hypothesis is true, then there are polynomial time
    deterministic tests for primality [2]. This is fascinating from a
    theoretical point of view, but in practice it would make no difference:
    the randomized algorithms are good enough.

    In any case, there is a polynomial-time primality test that doesn't
    depend on the Riemann Hypothesis [1]. But perhaps this is too recent
    (2002) to have made it into the book (published 2003-04-29).

    And finally, a faster primality test doesn't affect the security of RSA:
    you need a faster factorization algorithm for that.

    [1] M. Agrawal, N. Kayal and N. Saxena, PRIMES is in P, 2002.
        http://citeseer.nj.nec.com/agrawal02primes.html
    [2] L. Miller. Riemann's hypothesis and tests for primality.
        J. Comput. Sys. Sci., 13:300--317, 1976.
    [3] M. O. Rabin. Probabilistic algorithm for testing primality.
        J. Number Theory, 12:128--138, 1980.
    [4] R. Solovay and V. Strassen. A fast Monte-Carlo test for
        primality. SIAM Journal on Computing, 6:84--86, 1977. 

    -- 
Gareth Rees
  • Next message: Stephen Harris: "Re: Church-Turing compared to Zuse-Fredkin thesis (two new papers)"

    Relevant Pages

    • As Stakes Increase, Prime-Number Theory Moves Closer to Proof
      ... The English mathematician G.H. Hardy was an avowed atheist, ... the early 20th century the Riemann hypothesis had become a Holy Grail ... This last string is curious because the primes in it all are separated ... two mathematicians proved that there exist strings ...
      (sci.math)
    • Re: Cant wait to tackle the Riemann Hypothesis
      ... > There are oodles of theorems that go, "If the Riemann Hypothesis is ... > true then so is such and such an allegation about the primes," ... "The Millennium Problems: ...
      (sci.math)
    • Re: books on RH
      ... >following books: ... The Music of the Primes, ... >Unsolved Problem in Mathematics ...
      (sci.math)
    • Re: Cant wait to tackle the Riemann Hypothesis
      ... > erdosfan@yahoo.com (erdos fan) wrote: ... >There are oodles of theorems that go, "If the Riemann Hypothesis is ... >true then so is such and such an allegation about the primes," ...
      (sci.math)