best way to do "fermat" primalty checks

Torbjorn Granlund tege at
Sun Nov 13 20:28:23 CET 2005

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

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 mailing list