best way to do "fermat" primalty checks
juergen.bullinger at gmx.net
Sun Nov 13 18:57:45 CET 2005
Hi Dècio and all others,
thank you for your quick answer!
My numbers are all of the form p*n+1 where p is a prime and 2<=n<=p.
Because of this it is possible to proof primality just using the "fermat
check" and one additional gcd-check.
I am not familiar with the miller rabin test, but from what I read about
it, I think it would not be faster than the fermat check, because it
repeats something like a fermat check several times. Am I right?
Is there anybody who can tell how much a special powm-function with a
fixed base of two would be faster than the normal powm-function?
Do you expect any difference at all?
Juergen Bullinger <juergen.bullinger at gmx.net>
More information about the gmp-discuss