best way to do "fermat" primalty checks
Décio Luiz Gazzoni Filho
decio at decpp.net
Sun Nov 13 21:20:21 CET 2005
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.
> 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.
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20051113/4c31742a/PGP.bin
More information about the gmp-discuss