# probab_prim_p

**Kevin Ryde
**
user42@zip.com.au

*Thu, 31 Jul 2003 09:06:47 +1000*

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.