best way to do "fermat" primalty checks

Juergen Bullinger juergen.bullinger at
Sun Nov 13 17:58:06 CET 2005


I need to do compositeness checks on very large numbers (thousands of
At the moment I use trial divisions and termat checks (2^(p-1) ?= 1 (mod
* At the moment I use mpz_powm for this purpose, but I wonder if there
is a better/faster way to do that, because for me it is sufficient to
use 2 as the base (mpz_powm(resultVar, 2, phiVar, prime)).
I know that there are functions with base 2, but it looks that they are
all using long integers as an exponent, but I need larger exponents.

Thank you in advance

Juergen Bullinger <juergen.bullinger at>

More information about the gmp-discuss mailing list