mpz_probab_prime_p probability?

Torbjorn Granlund tg at
Sun Jul 8 00:33:50 CEST 2012

Sam Kennedy <samstauk at> 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

So for 7 repetitions you'll get 99.994% likelyhood even for the worst

  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.


More information about the gmp-discuss mailing list