probab_prim_p

[Clemente Galdi]

 Hi, 

> 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).
 
 Well, it depends on what you mean by "quick". 
 There is, indeed, a recent solution to the problem PRIMES in P by some
indian researchers. 
 You can download the paper from
 http://www.cse.iitk.ac.in/news/primality.html

 The complexity of the solution is polynomial in the size of the prime,
that is a huge result w.r.t. previous ones.
 Of course, any probabilistic algorithm is much faster than that, also
because the exponent of the polynomial seems to be around 6, that for huge
numbers means a lot of work.
 
 Anyway, there are different implementations of this algorithm and at
least one of them uses gmp. (Unfortunately for our friend who started this
thread... it's in C++.)
 Give a look at http://fatphil.org/maths/AKS/ for further info.

--clemente