best way to do "fermat" primalty checks

Décio Luiz Gazzoni Filho decio at
Sun Nov 13 17:24:07 CET 2005

On Nov 13, 2005, at 2:58 PM, Juergen Bullinger 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)).

GMP has functions for that, which applies trial division and Miller- 
Rabin (strong) PRP tests. (I found this info here: http://, but wouldn't  
it be more natural to put it in the `Algorithms' section of the manual?)

Anyway, the function that performs pseudoprimality tests is  
mpz_probab_prime_p, and the function mpz_nextprime might also be of  
interest. The man page for these is

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url :

More information about the gmp-discuss mailing list