probab_prim_p

delta trinity deltatrinity@hotmail.com
Fri, 01 Aug 2003 08:37:51 -0400

```>From: Kevin Ryde <user42@zip.com.au>
>
>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.

If you want to actually proove that a number is prime, it may get very
complicated, depending on the size ond form of the number.  There is no
known quick 'prime prooving' algorithm (by 'prooving', I meen actually
cathematicalle/computationally prooving, out of any doubth).

All the fast *probabilistic* 'prime prooving' algorithm to day actually can
proove only one thing, it's the compositeness of a number.  That is, it can
proove out of any doubth if a number is composite.  As the number grow, it
may miss a few composite (and report that it's prime) but will never tag a
prime as a composite.  Also, as the number to test grow, and the number of
loop you're telling the algorithm to do, the chance that the algorithm fail
decrease exponentioally (it will report less and less composite as a prime).
The chance that a 50 digit number, given 10 iterration of the algorithm,
get tagged as prime when it's really a composite is really really slim,
thus, the the number that get tagged as probable prime can be taught as an

Prooving primeness is computationally intensive.  I can suggest you a book,
called 'Prime Numbers, a computational perspective' (Richard Crandall & Carl
Pomerance) ISBN 0-387-94777-9.  It's really great at explaining all this
stuff, and many other things like number theory, factoring (cover a lot of
algorithm, starting with exponential, then, sub-exponential, like quadratic
sieve, elliptic curves, number field sieve, all in great details), ...  Note
that if you're really an algorithm nuts, you could always try to implement
(and, first, try to understand), ... And explained in a computational way,
actually intended with 'how to code this on a computer' in mind.  I very
liked that book and keep it as a good refference book.

Eric

_________________________________________________________________
STOP MORE SPAM with the new MSN 8 and get 2 months FREE*
http://join.msn.com/?page=features/junkmail

```