Décio Luiz Gazzoni Filho
decio at decpp.net
Tue Nov 15 18:14:03 CET 2005
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
More information about the gmp-discuss
mailing list