mpz_probab_prime_p() failures

[Sisyphus]

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

Without actually checking, I think there's a number of sources (eg 'Handbook
of Applied Cryptography") that specify this - mainly as a
means to avoid being deceived about the primality of specially constructed
numbers that one might have been handed. If the bases that one is going to
use are not known in advance, then such a deception would probably not even
be attempted (and if it were attempted, fail).

But, yeah - I overstated as, in general, there's *no* obligation to use
random bases. On the other hand, in the general sense, there's no obligation
to *not* use random bases, either.

It just doesn't seem right to me that mpz_nextprime() *inevitablty* reports
that the first prime greater than 209881968380913401 is (the composite)
209881968380913403. But, I guess there are other solutions to that - such as
increasing the number of Miller-Rabin tests that mpz_probab_prime_p()
conducts.

If mpz_nextprime() can come up with the composite 209881968380913403, then
it's apparently performing less than 12 miller-rabin tests. Is that
reasonable for such a small number ?

> 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