probab_prim_p

[Kevin Ryde]

Katrin Peter <katrin@pcpool00.mathematik.uni-freiburg.de> writes:
>
> I use your gmp library for a c source code. Iwant to verify the
> goldbach conjecture between 10^24 and 10^25. For this I use the
> function mpz_probab_prim_p. Where can I find the implementation for
> the function

The source is mpz/pprime_p.c.  The notes below on the algorithm will
be in the next release of gmp too.

> and do you know how I can certificate my numbers as
> prime (not probably prime) I would be very happy to get an answer.

Currently gmp doesn't have any actual prime proving.  Prime testing is
a biggish field and covering it fully is likely to remain beyond our
scope.


Prime Testing
-------------

The primality testing in `mpz_probab_prime_p' (*note Number Theoretic
Functions::) first does some trial division by small factors and then
uses the Miller-Rabin probabilistic primality testing algorithm, as
described in Knuth section 4.5.4 algorithm P (*note References::).

   For an odd input n, and with n = q*2^k+1 where q is odd, this
algorithm selects a random base x and tests whether x^q mod n is 1 or
-1, or an x^(q*2^j) mod n is 1, for 1<=j<=k.  If so then n is probably
prime, if not then n is definitely composite.

   Any prime n will pass the test, but some composites do too.  Such
composites are known as strong pseudoprimes to base x.  No n is a
strong pseudoprime to more than 1/4 of all bases (see Knuth exercise
22), hence with x chosen at random there's no more than a 1/4 chance a
"probable prime" will in fact be composite.

   In fact strong pseudoprimes are quite rare, making the test much
more powerful than this analysis would suggest, but 1/4 is all that's
proven for an arbitrary n.