# mpz_millerrabin

Niels Möller nisse at lysator.liu.se
Wed Jan 23 09:01:52 CET 2008

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

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