Re: Riemann Hypothesis and P vs NP

From: Jean-Luc Cooke (jlcooke_at_engsoc.org)
Date: 07/05/04 

Date: 5 Jul 2004 14:25:28 GMT

In sci.math Chairman of the Ozzy Osbourne Appreciation Society <mathgeekxxxxii@hotmail.com> wrote:
> 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.

> 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."

Yes. It's down from 4 to 2. And the MR test (I'm old fashioned so I'll
call it the Strong Pseudo Prime test) will prove an N composite. But
this isn't proving it's prime. And as many other said (for the benefits
of other reading) this does not lead to factoring.

For the lay:
  There are 3 problems at work here:
   1) Factoring
   2) Prime testing
   3) Composite Testing

Most crypto uses many tests of type (3) do deduce with high confidence
that a number is prime (hence replacing the expensive test of type (2))

Once RSA keys are chosen, you need to use an algorithm of type (1) which
is even harder (as far as we know) than (2).

We've found a P-time (2), but the constant infront is so huge that
it's not practical for numbers < 2^100,000 ...maybe larger.

We've got a few NP-time algorithms for (1)

We've got several P-time (3)'s but they arn't as interesting as (1) and
(2) - though currently far more usful.

> "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.

Yes, truly evil. This person should consider a carreer in advertising.

JLC 

--

Relevant Pages

  • Re: EFFICIENCY: PRIME TEST vs PRIME GENERATOR
    ... > Let's suppose we have an algorithm that will take a positive ... > For example, the USUAL test runs on odd numbers, checking for primality. ... > The time it takes to prove one such number is either composite or prime is ... > you DON'T use every partition, you might require very large exponents. ...
    (sci.math)
  • Re: Primes algorithm
    ... > method which is generally used, as far as I know, is the Miller-Rabin ... > algorithm, ... > that a given number is composite, then it is definitely composite; ... A number is prime with a probability equal to either 0 or to 1. ...
    (sci.crypt)
  • Re: Towards a Formula for Primes
    ... did the OP prove that this algorithm always makes primes? ... which are either composite, or not necessarily prime ... it certainly comports to Big Peak Oil's statistics -- ...
    (sci.math)
  • Re: Probabalistic algorithms.
    ... >Hashing is typically just an optimisation. ... all the hash does is guarantee that given some ... >hard to factor the composite into its two prime factors. ... >algorithm that's dfaster than brute force factorisation, ...
    (comp.lang.pascal.delphi.misc)
  • Re: Riemann Hypothesis and P vs NP
    ... However I did check to see if the algorithm ... call it the Strong Pseudo Prime test) will prove an N composite. ... Prime testing ... We've got several P-time 's but they arn't as interesting as and ...
    (sci.math)