best way to do "fermat" primalty checks
tege at swox.com
Sun Nov 13 20:28:23 CET 2005
Juergen Bullinger <juergen.bullinger at gmx.net> writes:
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?
I don't think the fact that the base is 2 could allow for any
shortcuts. However, all small bases could allow for somewhat
If somebody would want to try to write a special mpz_powm for
that case (perhaps mpz_ui_powm) that would be a welcome
contribution to the GMP project.
More information about the gmp-discuss