mpz_probab_prime_p probability?

[William E. Skeith III]

Hi Sam and Torbjörn,

>   I was wondering about the probability of composite-ness with the
>   mpz_probab_prime_p function and the number of reps.
>  
>   For the miller-rabin test, if *m *is the number of randomly selected
>   integers to be used as 'witnesses', the probability of a potential prime
>   being prime is: 1-(0.5)^m
>  
> Not quite.  For certain numbers, 25% of the bases will "bear false
> witness" of primality.  Most numbers will have *much* fewer liars than
> 25%.
> 
> So for 7 repetitions you'll get 99.994% likelyhood even for the worst
> numbers.

There was a nice paper by Damgard, Landrock and Pomerance some time ago
that bounded the false positive rate, where the probability was taken
over the number of trials, _as well as the random selection of an n-bit
integer_.  The results are quite strong (I was impressed, anyway).  You
can find the details in their paper here:

http://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1189518-9/S0025-5718-1993-1189518-9.pdf

It sounds like Torbjörn is already familiar with this result, but I
thought I would share it anyway, just in case.

-WES