> 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 :-).
I doubt that efforts in the direction of a deterministic polynomial time algorithm
will look bad at all. Due mainly to the fact that Miller's test is not very
practical.
> 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.
What? I thought (I could be wrong) that this had something like a log(log(log(n)))
term in the exponent which prevented it from being polynomial. There are many
deterministic algorithms (trial division for example), but you have to accept
*very* bad run times.
-Lucas
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
