mpz_probab_prime_p() failures
Jim Fougeron
jfoug at cox.net
Mon Dec 5 12:59:08 CET 2005
>> PFGW, arguably the fastest pseudoprimality testing software
>> for x86 platforms, and well respected by experts, uses only base 3
>> unless explicitly asked for a different base.
>
> Just curious - why did they choose 3, as opposed to any other small number
> (eg 2) ?
>
>
> Cheers,
> Rob
>
The choice for base 3 PSP test (Fermat test, not SPSP miller test), was due to history where
most people searching for huge primes (what PFGW was designed for) were searching
for primes in the k*2^n+-1 range. For numbers of the form 2^n+-1 using a Fermat base-2
test is quite surprising ;) Also, within our FFT engine, using a base of 3 vs 2 makes no speed
differenece at all. In fact, any "tiny" base, can be used, and adds zero time, in fact the
multiplication phase of a exponentiation step (the square-multiply-reduce), is done "inline"
within the reduction step for a cost of O(n)
Also, even though PFGW was advertised as "arguably the fastest pseudoprimality testing
software for x86 platforms", I would argue here, for this problem, that PFGW is a terrible
choice (much much worse than a custom GMP mpz_probab_prime_p() written chunk
of software). In fact for number this size (actually numbers much larger than this, say
up to 2^1000 or so), pfgw actually uses gmp's mpz_powm() function to perform it's
"testing". However, note there is a HUGE amount of overhead in PFGW (in relation to
the amount of time needed for a mpz_powm() call at the 2^64 size), thus your throughput
with PFGW is significantly less than a custom app (probably only 5% to 10% of the
runtime will be used in the mpz_powm calls) thus 90% to 95% of the time is "wasted"
in other housekeeping issues within PFGW. Now when working on slightly larger numbers,
say 117*2^850123+1 to 499907*2^850123+1 or the other 12991 k values (k*2^n+1)
inbetween which have no factor less than about 3 billion, then the overhead in PFGW is
trivial (less than 0.01% total runtime). Note the above sized numbers are the kind PFGW
likes to chew on :)
Note, even though I am one of the main developers of PFGW, and have it running
24/7 on dozens of PC's, when I want to work on smaller numbers, (say 2^150 or so in
size), I almost never use PFGW (unless just testing a small sample), and revert back
to writing a GMP app, where I can control the IO overhead, and other housekeeping
overhead.
Jim.
Tray Helper - try to find something more useful... (http://www.trayhelper.com)
More information about the gmp-discuss
mailing list