gmp-discuss Digest, Vol 28, Issue 6

[Jim Fougeron]

>> 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)