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