On 4 Nov 99, at 10:20, Preda Mihailescu wrote:
> This is not correct. ECPP is polynomial, but it is _not_ deterministic, in fact
>pretty
> far from that. We are currently working at a deterministic polynoial time algorithm.
> It requires some additional spices, compared to ECPP.
Gary Miller has demonstrated that, given the Generalized Riemann
Hypothesis, at most 2(ln n)^2 probabalistic prime tests (aka Miller's
Tests) suffice to determine the primality of n. This gives a
"straightforward" deterministic polynominal time algorithm - though
the performance is rather poor compared with the Lucas-Lehmer test
for Mersenne numbers, the Pepin test for Fermat numbers or Proth's
Test for the eponymous numbers.
Miller's result yields a direct method of disproving the GRH - simply
find a counterexample. I wouldn't hold my breath waiting for a
counterexample to be found, though.
Regards
Brian Beesley
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
