mpz_probab_prime_p() failures

[Décio Luiz Gazzoni Filho]

On Dec 4, 2005, at 9:41 PM, Sisyphus wrote:

>
>>
>> FWIW, Thomas Nicely maintains a list of mpz_probab_prime_p failures
>> at http://www.trnicely.net/misc/mpzspsp.html
>>
>
> That's interesting. For some reason I thought that  
> mpz_probab_prime_p() did
> a fermat test (base of 2) after the trial divisions - yet nearly  
> all of
> those numbers are reported composite by such a fermat test. (Not  
> sure where
> I got that notion from. On re-reading the GMP docs I can't find any
> reference to fermat tests wrt mpz_probab_prime_p).
>
> It's a little disconcerting to me that mpz_netxprime() also throws  
> up the
> very same composites as being prime. (It doesn't start getting it  
> right
> until we get down to 25366866661.)
>
> For the little extra overhead, wouldn't it be worth having the  
> bases of the
> miller-rabin test pseudorandomly determined, rather than pre-set ?

But then you get the problem that your pseudo-random number generator  
might choose 2 the moment you're testing 2047 and suddenly you can  
get really small 11-bit composites being reported prime.

By choosing pseudo-random values, the problem will not go away --  
you'll just randomize it, which in my opinion is much worse. At least  
with a preset choice of basis I can for instance have piece of mind  
that, say, all 32-bit composites are properly detected.

> Just using C's rand() function seeded with some combination of  
> (last few
> digits of) timestamp and pid would suffice (I think). This would  
> then be in
> keeping with the way that probable primality tests *ought* to be  
> conducted -

Says who? 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. Of course it's usually  
employed for much larger numbers, but then again, if one is testing  
small integers and so concerned about failures in a compositeness  
test, writing a BLS primality (not pseudoprimality) test is certainly  
worth the effort, and won't detract much from performance (unless  
you're a serious prime hunter testing thousands or millions of small  
integers per second, in which case you should be writing custom code  
and yes, perhaps even using these `dirty' tricks with compositeness  
tests).

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/20051205/b23ac6d8/PGP.bin