View Single Post
Old 2002-11-05, 01:26   #2
ewmayer's Avatar
Sep 2002
Rep├║blica de California

5·7·331 Posts

The short answer is: no.

There is some discussion and links in the Math thread titled

AKS - A polynomial-time algorithm for testing primality.

The main significance of the AKS algorithm is that it is the first *provably*
polynomial-time scheme for proving primality (or not) of any desired number.
That doesn't mean it's necessarily faster in practice than schemes such
as ECPP, which are polynomial time for nearly all inputs (and many such schemes
are in fact polynomial time for ALL inputs if the Extended Riemann Hypothesis
is true - it probably is, but AKS doesn't need it to be). And for numbers of
special form (e.g. Mersennes, Fermats, Proths, etc.) there are well-known
deterministic primality tests that are not only polynomial time, but also
much faster than AKS, ECPP, etc. So don't expect to replace Prime95 with
anything else just yet. :)

ewmayer is offline   Reply With Quote