probable prime tests for gmp

Torbjorn Granlund
04 Nov 2002 15:35:04 +0100

Jason Moxham <> writes:

  On Thursday 31 Oct 2002 12:14 am, Kevin Ryde wrote:
  > Jason Moxham <> writes:
  > > Again if a user
  > > wants a pure strong psuedoprime test then he will have to write one for
  > > himself , or gmp will have to provide both ?
  > Don't know.
  > I guess the potential strengthening of tests in tricky ways is a good
  > argument for not exposing particular components like mpz_millerrabin.
  > An interface that's highly specific to a particular algorithm is
  > instantly obsoleted by an advance in the theory.
  But if an advance of theory takes say 10 years , then we will be
  stuck with a generic interface.  Something like
  "mpz_probable_prime_p" should be independant of the particular test
  , so that we can take advantage of any new theory , and could also
  have "mpz_sprp" and "mpz_rqft" for people or algorithms that need a
  particular test for whatever reasons. mpz_sprp allready has good
  reason for being exposed (crypto)
We want a generic function, but with a better interface than the
current mpz_probab_prime_p.  A probability argumetn is much better
that a repeat count.

We might also want a restartable interface.  For some applications, it
might be useful to find a few likely primes, then determine with much
higher probability that certain numbers are really prime.

Not sure about lots of specific functions, like mpz_sprp,
mpz_millerrabin, etc.