mpz_probab_prime_p probability?
William E. Skeith III
wes_zilla at yahoo.com
Sun Jul 8 08:22:34 CEST 2012
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
More information about the gmp-discuss
mailing list