Slashdot Mirror
Fun with Prime Numbers
Steve Litt writes "Fun
With Prime Numbers contains a series of prime number finding algorithms starting with the most brute force imaginable, and working up to a paged algorithm capable of finding the first 1,716,050,469 primes in an hour and a half on a commodity machine. There are faster algorithms on the net, but these algorithms are within the reach of mere mortals and are fully explained."
Google Cache
Mom says my
A very fast segmented sieve (to find primes in an arbitrary range) can be found here, by Tomás Oliveira e Silva.
Of tangential interest is his Goldbach conjecture verification project. You can download his client and contribute to the project. He's shooting for 10^18...
Find out more on the Nth Prime Page.
encryption.
"It is not how things are in the world that is mystical, but that it exists." -Ludwig Wittgenstein
There are a lot of them.
As a matter of fact 2048 bits can represent numbers up to 2^2048 ~= 3.23x10^616. By the Prime Number Theorem there is about 2.27x10^613 primes in that space. If each prime required 2048 bits to store, then storing all the 2048 bit primes requires more petabytes then you and I are likely to ever see.
(Jeez I hope I didn't do the math wrong. The most convenient calc I have available to me as I write this in the Windows calc)
You are not a beautiful or unique snowflake -- but you could be if you got off your ass.
I'd venture to say I know what I'm talking about. One can't publish a paper about large-scale distributed primality proofs without knowing these basics. Here's a sample of my work. Now don't get me wrong, I'm not trying to sound like a smart-ass, but I'm not going to let someone question my knowledge in this field (which I have studied for years) and remain quiet.
Now it seems people here are not familiar with the terminology associated with Mersennes, so I'll give a crash course.
A Mersenne number M_n is of the form 2^n - 1. If 2^n - 1 is prime, then M_n is a Mersenne prime. If 2^n - 1 is composite, then M_n is a Mersenne composite. The integer n in this expression is called the exponent. When I talk about `exponents of Mersenne composites', I'm refering to some prime n for which M_n = 2^n - 1 is composite.
Now if 2^n - 1 is prime, then n must be prime, but the converse is not always true, the smallest counterexample being 2^11 - 1 = 2047 = 23*89. Turns out that for prime exponents n = 24,036,583, only in 41 cases is 2^n - 1 actually prime. A list of these cases can be found here. For the other 1,509,222 prime values of n = 24,036,583, 2^n - 1 is composite. This translates to a compositeness ratio of 99.9973%.
I hope everything is clearer now.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
You overlooked another key optimization - no number can have prime factors larger than sqrt(N). You don't need to bother computing any of the intermediate primes. With a 210-into-48 encoding you can quickly determine primality of any 32-bit number with a precomputed block of only 2k! This is such a small buffer that you could easily bootstrap it the first time the function is called - you can bootstrap the process by hardcoding nothing more than the first 6 bytes.
This raises an interesting question - is it faster to load precomputed blocks from disk or to regenerate it in the L1 cache? One buffer would hold the first block, a second buffer would hold the 2nd-Nth block computed on demand, and a third buffer would hold the target block that's being updated by each successive block.
For every complex problem there is an answer that is clear, simple, and wrong. -- H L Mencken
On my computer, generating primes from 2 to 2^32 takes a third of the time to unbzip2 the same list.
That's where you represent primality or lack of it by setting and clearing bits of an integer.
... there is an even more efficient representation: just write out the prime gaps, i.e. the difference between consecutive primes.
Working out the mask for those bit operations can take enough time to cancel out the space benefits. I think you could optimize the different masks & their steppings.
I tried this, but I don't know where that program is now. I used 0 as an escape code, allowing me to either note the next delta in hex, or else the current number, to detect errors. I only did this for output, though.
I could see that being effective for the trial factor prime number table, too.
Oh, and the nfsnet thing that's your homepage is cool.
There's a primes program in (uh, on Debian) the bsdgames package; if memory serves, it does the wheel thing suggested.
A suggestion for the article:
If the trial factor prime number table gets big enough to swap (either out of cache, or out to disk), just segment the trial factors too.
This is something I've given a lot of thought to; I've been interested in prime numbers since I was a kid. I've thought about making CDs or DVDs full of primes.
Of course, if you absolutely have to be sure that you're dealing with a prime, you could use a probabilistic algorithm to sieve for probable primes, then apply the n-1 test to obtain a primality certificate for your probable prime (which then becomes a certified prime with 0% probability of being composite). Of course this would be a bit costly, but for small integers the n-1 test is hard to beat -- ECPP and APR-CL have just too much overhead at this range. But I'm pretty sure your application, whatever it is, can live with the small probability that a PrP is composite.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
Covering 30 numbers per byte and precomputing all the bit-indices, one arrives at: http://www.cwi.nl/~tromp/pearls.html#sieve