best way to do "fermat" primalty checks

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


Juergen,

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
application?

-Ted

On 11/13/05, Juergen Bullinger <juergen.bullinger at gmx.net> 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 gmx.net>
>
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at swox.com
> https://gmplib.org/mailman/listinfo/gmp-discuss
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://gmplib.org/list-archives/gmp-discuss/attachments/20051113/f2a4321a/attachment.html


More information about the gmp-discuss mailing list