probable prime tests for gmp
Torbjorn Granlund
tege@swox.com
04 Nov 2002 15:35:04 +0100
Jason Moxham <J.L.Moxham@maths.soton.ac.uk> writes:
On Thursday 31 Oct 2002 12:14 am, Kevin Ryde wrote:
> Jason Moxham <J.L.Moxham@maths.soton.ac.uk> 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.
--
Torbjörn