# best way to do "fermat" primalty checks

Décio Luiz Gazzoni Filho decio at decpp.net
Sun Nov 13 19:49:58 CET 2005

```First of all, the whole post is a non-sequitur. Nobody asked for a
lecture on primality testing.

It is also factually incorrect:

On Nov 13, 2005, at 3:42 PM, Emanuele Laface wrote:

> But if you need something of special I can say that the best algorithm
> to check primality is the Agrawal, Kayal, Saxena (or AKS) test.

Nonsense. AKS is so horribly slow as to be useless, last I heard.
ECPP is the best choice for general-purpose primality proving. If you
and records using it, as I will provide for ECPP: the software is
and the record is 7993 decimal digits (http://www.ellipsa.net/primo/
record.html), not to mention François Morain's successes with
clustered ECPP (I believe he's up to 15k digits).

> It is based on little fermat theorem and is polinomial in the
> number of ciphers.
> The main problem of this algorithm is that use the polinomial
> division, and I don't know a fast way to implement them. So the
> algorithm is theoretically polinomial but all implementation that I
> saw (I also wrote one by myself) are very slow respect to
> probabilistic algorithms.

Also nonsense. The AKS algorithm is polynomial (hence `efficient'
according to complexity-theoretic measures) whether you use grammar-
school polynomial multiplication or fast FFT techniques. `Polynomial'
and `exponential' are complexity-theoretic labels to describe
theoretical efficiency of algorithms, which are often unrelated to
performance in practice. To witness, the APR-CL primality proving
algorithm has subexponential complexity but completely spanks AKS for
any range of practical interest.

Oh, and AKS is slow not only in comparison to PRP tests, but to ECPP
as well, hence it is a poor choice as I stated above.

Décio

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20051113/287eee9e/PGP.bin
```