best way to do "fermat" primalty checks
tjdziuba at gmail.com
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 gmx.net> wrote:
> 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 gmx.net>
> gmp-discuss mailing list
> gmp-discuss at swox.com
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the gmp-discuss