best way to do "fermat" primalty checks

[Décio Luiz Gazzoni Filho]

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:// 
www.swox.com/gmp/manual/Number-Theoretic-Functions.html, 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

http://www.swox.com/gmp/manual/Number-Theoretic-Functions.html

Décio
-------------- 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 : http://gmplib.org/list-archives/gmp-discuss/attachments/20051113/da128d16/PGP.bin