best way to do "fermat" primalty checks

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


Hello,

I need to do compositeness checks on very large numbers (thousands of
bits).
At the moment I use trial divisions and termat checks (2^(p-1) ?= 1 (mod
p)).
* 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

-- 
Juergen Bullinger <juergen.bullinger at gmx.net>



More information about the gmp-discuss mailing list