mpz_probab_prime_p probability?
Torbjorn Granlund
tg at gmplib.org
Sun Jul 8 00:33:50 CEST 2012
Sam Kennedy <samstauk at gmail.com> writes:
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.
So for a value of 7, the probability of being prime is 99.2%
I was wondering if this was the same for the function in the gmp library?
The function is documented as using Miller-Rabin tests.
--
Torbjörn
More information about the gmp-discuss
mailing list