ECPP is the fastest known general-purpose primality testing algorithm. ECPP has a running time of O(ln(N)^4).
As of 2004, the program PRIMO can certify a 4769-digit prime in approximately 2000 hours of computation (or nearly three months of uninterrupted computation) on a 1 GHz processor using this technique. As of 2003, the largest prime certified using this technique had 6959 decimal digits and required 12658 CPU-hours on a 1.4 GHz Athlon (Martin).
http://mathworld.wolfram.com/EllipticCurvePrimalityProving.html
See also
http://mathworld.wolfram.com/Pollardp-1FactorizationMethod.html for a simpler but still quite complex method that doesn't involve elliposids factoring.
PS
To run your algorithm alot faster for most optimising compilers:
1. check for N = 0, 1, 2, 3 or even - to speed things up
2. take the sqrt out of the loop invariant test, make it the starting loop value if its not a trivial test caught above
3. The loop if it is reached will run at least once so make the conditional test last - implying use a do..while loop rather than a for () or while () loop, will save one test vs other loop options
4. use !(N) to test for N==0, bitwise NOT is often faster than a compare to 0 on many compilers
5. wherever you have x*2^a use x<<a (left shift) so 2*x = x<<1 its faster using bitwise operations
6. the loop decrement can be moved into the if test as i-- or used in the loop conditional as while (--i) - note compilers are good with decrement skip on 0 loops optimisations
Code:
boolean IsPrime(unsigned long N){ register int i;
(N < 2 || !(N%2) )? return false : (N < 4)? return true : i=round(sqrt(N)/2);
do
if (!(N%((i<<1)+1)) ) return false;
while ( --i );
return true;
}
If you want probablistic sampling algorithims (so you trade certainity of a prime for confidence intervals) see
http://mathworld.wolfram.com/PrimalityTest.html
for good background on this.
Primality Test
A primality test is a test to determine whether or not a given number is prime, as opposed to actually decomposing the number into its constituent prime factors (which is known as prime factorization).
Primality tests come in two varieties: deterministic and probabilistic. Deterministic tests determine with absolute certainty whether a number is prime. Examples of deterministic tests include the Lucas-Lehmer test and elliptic curve primality proving. Probabilistic tests can potentially (although with very small probability) falsely identify a composite number as prime (although not vice versa). However, they are in general much faster than deterministic tests. Numbers that have passed a probabilistic prime test are therefore properly referred to as probable primes until their primality can be demonstrated deterministically.
The Rabin-Miller strong pseudoprime test is a particularly efficient algorithm used by Mathematica's PrimeQ function. Like many such algorithms, it is a probabilistic test using pseudoprimes. In order to guarantee primality, a much slower deterministic algorithm must be used. However, no numbers are actually known that pass advanced probabilistic tests (such as Rabin-Miller) yet are actually composite.
Unlike prime factorization, primality testing was long believed to be a P-problem (Wagon 1991). This had not been demonstrated, however, until Agrawal et al. (2002) unexpectedly discovered a polynomial time algorithm for primality testing that has asymptotic complexity of O(ln(N)^12) (Bernstein 2002, Clark 2002, Indian Institute of Technology 2002, Pomerance 2002ab, Robinson 2002). Their algorithm has come to be called the AKS primality test.
http://mathworld.wolfram.com/Atkin-Goldwasser-Kilian-MorainCertificate.html
Stumble It!
Tweet This
Bookmark on Delicious
Share on Facebook
Share on MySpace