mpz_millerrabin

[Niels Möller]

Paul Leyland <paul at leyland.vispa.com> writes:

> If one knows nothing about an integer N, other than it is not divisible
> by any small primes (and all primes are small if it's required that N is
> to be tested against all smaller ones) then it is overwhelmingly likely
> that a single test to a randomly chosen base in the range 3 to N-3 will
> correctly indicate that N is prime.  (Avoiding 0, \pm 1 and \pm 2 mod N
> is a good idea...)

If one should avoid using 2 as a base for the test, does that imply
that one should also avoid 4, 8, and other (small?) powers of two?

Do you know if there are any results when you select the bases
deterministically (say, 3, 5, and 7)? The number N naturally still has
to be selected by some random process, for probalities to make any
sense in this setting.

> I don't have the reference to hand which documents these probabilities. 
> I can dig it up and post it if anyone would prefer me to perform the
> Google search.

Are these the same reference you are refering to? From the wikipedia
entry: 

  On average the probability that a composite number is declared
  probable prime is significantly smaller than 4  k. Damgård, Landrock
  and Pomerance compute some explicit bounds. Such bounds can for
  example be used to generate primes, but should not be used to verify
  primes with unknown origin. Especially in cryptographic application an
  adversary might try to send you a pseudoprime in a place where a prime
  number is required. Then only the bound 4^-k can be relied upon at
  this time.On average the probability that a composite number is
  declared probable prime is significantly smaller than 4^-k. Damgård,
  Landrock and Pomerance compute some explicit bounds. Such bounds can
  for example be used to generate primes, but should not be used to
  verify primes with unknown origin. Especially in cryptographic
  application an adversary might try to send you a pseudoprime in a
  place where a prime number is required. Then only the bound 4^-k can
  be relied upon at this time.

[...]

  I. Damgård, P. Landrock and C. Pomerance (1993), Average case error
  estimates for the strong probable prime test, Math. Comp. 61(203)
  p.177194.

I haven't thought this through, but the adversarial argument seems
fairly important to me.

Regards,
/Niels