best way to do "fermat" primalty checks

Ted Dziuba tjdziuba at
Sun Nov 13 17:25:59 CET 2005


You may want to consider a probabilistic method such as the Rabin-Miller
test. This test can be performed very quickly, and some variations on it
make it very accurate. How important is proof of primality in your


On 11/13/05, Juergen Bullinger <juergen.bullinger at> wrote:
> 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>
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at
-------------- next part --------------
An HTML attachment was scrubbed...

More information about the gmp-discuss mailing list