>
> > 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
Sorry to contradict you, but this things are called ``deterministic under the
ERH'', which is totally different from deterministic, straight. The last
means an algorithm which gives a provable answer prime or composite
on any input, and the proof of which is complete (i.e. does not relay on
_any_ unproved conjecture). I agree, many experts believe the ERH is true,
but this does not change the notions, the way they are. Simply, if the ERH
is proved one day to be true, all the effort spent meanwhile for finding
deterministic primality proofs would look rather curly. But such is life.
I was in Rome this summer when the proof of the Taniyama conjecture
was announced, and at the same conference, in fact the day after the
announcement, there were several talks about ``elliptic curves which
are modular'', or ``Weyl curves'' - which were in that day known to be
simply all elliptic curves :-).
By the way there is exactly one deterministic primality proving algorithm
(general, i.e. yielding an answer for any input) known by this date, and
this is the deterministic version of the Adleman - Rumely - Pomerance test.
And as for your claim that Miller's proof would feature a contradiction to the
ERH, that is also false. In fact, what Miller noted is, that under the ERH, there
is a polynomial bounded quadratic non residue - as you mentioned - and it
follows without many complications, that beneath that bound, a Rabin-Miller
witness of compositeness must be found: so if you know ERH is true and you
performed Rabin - Miller tests up to that bound without encountering any
compositeness witness, you are certain n was prime. But now suppose that -
as it is in true life - you do not know ERH to be true. You do not find any witness
up to so and so much: what do you then know ? Do you have a contradiction to
the ERH ? Do you know n is prime ? Neither of both. On the other hand, if you use
a deterministic or Las Vegas test ending with an answer on your input then your
experiment shows:
a) that you did not find any contradiction to ERH, if the number was indeed prime,
but the Miller approach just could not give you a proof thereof (which he, of course
never claimed !) or
b) that you found a contradiction to the ERH if the other test proved n to be
composite.
Note that Las Vegas and deterministic tests always give correct unconditionally
provable
answers, the difference being that the last may also end with ``I do not know''.
Sincerely
Preda
> 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
