best way to do "fermat" primalty checks

Juergen Bullinger juergen.bullinger at
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?

Kind regards

Juergen Bullinger <juergen.bullinger at>

More information about the gmp-discuss mailing list