best way to do "fermat" primalty checks

[Décio Luiz Gazzoni Filho]

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  
disagree with this statement, please provide a link to AKS software  
and records using it, as I will provide for ECPP: the software is  
PRIMO by Marcel Martin (http://www.ellipsa.net/misc/downloads.html),  
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