Probability Bounds for mpz_probab_prime_p

[Torbjorn Granlund]

"Emil Stefanov" <emil at berkeley.edu> writes:

  Hello,
  
   
  
  I am considering using GNU MP for implementing cryptographic algorithms.
  However, the documentation for mpz_probab_prime_p does not provide any
  probabilistic bounds on n being composite by chance. Knowing these bounds is
  very important to ensure that an algorithm has sufficient cryptographic
  strength and is therefore secure.
  
   
  
  The documentation mentions that mpz_probab_prime_p uses the Miller-Rabin
  probabilistic primality test. Probablity bounds are well known for this
  algorithm (see
  http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test ). It would
  be great if the documentation could be updated to explain the correlation
  between the "reps" argument and the certainty parameter of the Miller Rabin
  primality test. Even better would be to provide a probability bound as a
  function of "reps".
  
You need to perform your own analyis of Miller-Rabin wrt your particular
numbers.  Then power your estimated error probability to reps...

-- 
Torbjörn