Re: Riemann Hypothesis and P vs NP

From: Chairman of the Ozzy Osbourne Appreciation Society (mathgeekxxxxii_at_hotmail.com)
Date: 07/05/04

  • Next message: Michael Varney: "Re: Infinity can not exist" 
    Date: Sun, 4 Jul 2004 20:42:12 -0400

    "*** T. Winter" <***.Winter@cwi.nl> wrote in message
    news:I0CoDw.BKp@cwi.nl...
    > In article <Yd0Fc.62723$OT6.26151097@news4.srv.hcvlny.cv.net>
    mathgeek42@hotmail.com writes:
    > ...
    > > > This does not depend on RH.
    > >
    > > Right, but the correctness of the algorithm I mentioned, did.
    >
    > I think the algorithm you refer to is Millers test. When the
    *generalized*
    > Riemann hypothesis is true, Miller-Rabin runs in polynomial time. If it
    > is false it is a probilistic test (or a long running non-probabilistic
    > test). On the other hand, polynomial time algorithms do exist, but much
    > slower than Miller-Rabin.

    When I eventually did get to check my copy of AC, I was frustrated to learn
    that I couldn't find the reference I was looking for, it seems very likely
    that
    I didn't originally come across it in Applied Cryptography, Ed 2.

    > > Well, My point was that the correctness of the algorithm
    > > (that I conjecture the OP was referring to...) for testing
    > > primality is provable if RH is true; and even if you prove
    > > RH is true, and the algorithm is in P, those two theorems
    > > alone aren't enough to reach the conclusion that P=NP.
    >
    > No, when RH is true that does not yet mean that Miller-Rabin is polynomial
    > time.

    I didn't name any algorithm, (including Miller-Rabin) because my memory
    was too fuzzy to recall a name. However I did check to see if the algorithm
    I thought I remembered even existed, which seemed like a good idea since
    it turned out that I couldn't find a reference to it from the book I
    _thought_
    that I had recalled it from.

    I found this post (among a few others) which seemed to indicate to me that
    such an algorithm does exist.

    http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&c2coff=1&selm=1991Nov20.190129.19640%40linus.mitre.org

    "There is a theorem due to G. Miller, which states that if the Riemann
        Hypothesis is true, then there will be a witness to the compositeness
        of n less than 4 log^2 n. I believe Eric Bach reduced the constant from
        4 to 2. This in turn yields a polynomial time prime testing algorithm
        (on R.H.). Its run time is O(log^3 n M(n)) where M(n) is the time
        to multiply two integers of size log n. M(n) = O(log^2 n) using naiive
        methods, and O(log n loglog n logloglog n) using FFT's."

    > For that you need the generalized RH. But indeed, whatever is the
    > case, the conclusion P=NP can not be reached that way.

    Ok. Good.

    > > Which is what was being suggested, or so I thought when
    > > I read:
    > > "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."
    >
    > And this is false. If the generalized Riemann Hypothesis is true there
    > is a very fast way to determine whether a number is prime. This does
    > *not* give a fast way to factorise numbers.

    Right. This is the second time someone emphasized that point,
    and I never said otherwise, but at least I now understand why
    people are pointing this out.

    I interpreted the following statement to mean _only_ that if RH is
    true, there is a sure, "fast" way to generate public/private key
    pairs.

    "there is a fast way to discover the primes used to build the RSA
    codes on which the security of e-business currently relies."

    I can see how his statement can be read to mean that RSA would
    become insecure. It's very possible that my interpretation was wrong
    but I felt: since the OP was concerned with an algorithm that tests for
    primality, that my interpretation was the natural one. Yet, I suppose
    on USENET it's probably safest to assume that the most sensational
    interpretation is the "natural" one.

    > --
    > *** t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland,
    +31205924131
    > home: bovenover 215, 1025 jn amsterdam, nederland;
    http://www.cwi.nl/~***/ 

    --
change Roman to Arabic numerals to email me
  • Next message: Michael Varney: "Re: Infinity can not exist"
    Loading