
Re: Largest primeproduct with 2 as factor?
Posted:
Aug 16, 2007 11:48 AM


jonas.thornv...@hotmail.com wrote:
> > Is the computional effort for primality test for x bigger or less than > checking that a composit only have two factors x*2?
I do not understand what you are asking. Please clairify. Modern algorithms check for primaility by first:
(1) Checking for small prime factors (2) Performing a probable prime test of some kind (3) Then proceeds to a full primality proof.
The AKS prime proving algorithms runs in time no worse than a constant multiple of (log N)^6 where N is the number you are testing. The multiple is machine and implementation dependent.
There is a random version that runs in time O( (log N)^4)
The cyclotomy primality test runs in time O( (log N)^ logloglog N)
May I suggest that you read a book on this subject? I can recommend a number of good ones.
You might start with:
H. Riesel Prime Numbers and Computer Methods for Factorization
The math in this book is well within the understanding of a good high school student.

