best way to do "fermat" primalty checks

[Décio Luiz Gazzoni Filho]

On Nov 13, 2005, at 5:43 PM, Emanuele Laface wrote:

> I don't really understand why you are offending me.

I'm not offending you, just being harsh since you posted an uncalled  
for reply which on top of it was factually incorrect.

> I wrote that AKS is the fastest deterministic theoretical algorithm
> because is the only deterministic in polynomial time.

No you didn't. There isn't a single instance of the word  
`deterministic' in your original email. And even if you did, the real- 
world doesn't care about `deterministic' -- the distinction between  
deterministic and randomized is merely academic and is a non-issue in  
the real world.

> Could you give
> me a counterexample?

Formally no, because there isn't another deterministic primality  
proving algorithm that runs in polynomial time. That doesn't mean  
that there aren't other efficient algorithms that prove primality,  
despite the fact that they make random choices (and hence are called  
randomized). Do not mistake those for probable prime tests or  
compositeness tests such as Fermat's test.

> I also said that practically is difficult to provide a fast
> implementation because in the algorithm there is a large use of
> division with polynoms that is difficult to implement in a fast way.

Which is part of the reason why AKS is useless and one should go for  
ECPP instead. Now what bearing does this have on the discussion and  
why did you have to repeat this again? I got it the first time.

> But, just to talk about primality, I thought that could be good to
> explain to the Bullinger that also exist this kind of algorithm.
> The worst crime that I performed could be the off topic but this don't
> justify your reaction.

Yes, your post was uncalled for -- but were that the only problem, I  
wouldn't have taken the time to reply. The factually incorrect  
statements of your reply were what compelled me to correct you.

>
> From the point of view of arrogance please let think that your are not
> the only person in the world that know something about algorithms,

Indeed, I never asserted that.

> I
> know perfectly the difference between P and NP.

Perhaps some day you'll also figure out that P and NP have little to  
do with real-world performance. Hopefully, along the way you'll learn  
that an algorithm being randomized is not necessarily a bad thing.

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/4c31742a/PGP.bin