[Décio Luiz Gazzoni Filho]

On Nov 15, 2005, at 2:36 PM, Jürgen Bullinger wrote:

> So in fact I don't need a more secure primality check. I just  
> wodered if
> there might be a faster check to sort out some composite numbers  
> just before
> I apply the FLT-check. I already do some sieving based on trial  
> divisions.

I don't know of any procedure, short of trial division, that can flag  
a composite more quickly than a Fermat test. Perhaps a factoring  
algorithm like Pollard rho or p-1 might find a small factor (that was  
nonetheless out of reach of trial division) faster than applying a  
Fermat test, but on average I don't think that's a good strategy. I  
should mention that there are algorithms like Jens Kruse Andersen's  
TreeSieve and D. J. Bernstein's product tree idea (essentially the  
same, don't know which of the two came up with the idea first) that  
are faster than standard trial division, but they're actually a form  
of trial division themselves, just changed a bit to better take into  
account fast multiplication algorithms.

Although that settles the question of testing a single number, if  
your goal is to find primes among a set instead of individually  
testing a single integer, you might try to use a sieving technique.  
The end result is the same as applying trial division to each integer  
individually, but the cost per element of sieving is much much smaller.

Oh, and may I persuade you to have a look at PFGW (http:// 
groups.yahoo.com/group/openpfgw)? Much as I like GMP the speed of  
PFGW is unbeatable, as Jim already alluded to.

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/20051115/7b78cdc4/PGP.bin