probab_prim_p

[delta trinity]

>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 
'industrial-grade prime'.

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