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."
EVER!!!
Google Cache
Mom says my
Rather, most of the Mersenne numbers are prime, and most of them are large. That doesn't begin to scratch the surface of most large prime numbers though.
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...
Well, considering that all positive integers > 1 are either prime themselves (e.g., 2, 3, 5, 7, 11...), or if not, can be expressed as the product of various primes (e.g., 4 = 2 * 2, 6 = 2 * 3, 8 = 2 * 2 * 2, 9 = 3 * 3, 10 = 2 * 5...), you could say that prime numbers are the building blocks of all integers, which is kind of cool...
Find out more on the Nth Prime Page.
The linked .txt file is 7.1 MB, so it probably will take a while. The Google cache doesn't do the number justice. In fact, the cached number is divisible by 2...
This site probably won't last long, heres google's cache:w w.troubleshooters.com/codecorn/primenumbers/primen umbers.htm+&hl=en/
http://66.102.7.104/search?q=cache:3EXdsF5PiA4J:w
He probably means that {sum of 1/n^x} = {product of 1/(1-1/p^x)}, where n runs over all integers, p runs over all prime numbers, and x > 1.
Wrong. There's more than 1.5 million primes up to 24,036,583 (the largest Mersenne exponent known), and only 41 of these are Mersenne exponents.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
encryption.
"It is not how things are in the world that is mystical, but that it exists." -Ludwig Wittgenstein
It has applications in abstract algebra (like group theory) and number theory. Besides cryptography, they are often used in pseudo-random number generators and hash tables. check out: http://en.wikipedia.org/wiki/Prime_numbers
take a class in abtract algebra, generally the first class in higher, proof-oriented mathematics. Primes have strong relevance in group theory (which is in itself relevant to quantum mechanics), which leads to rings and fields (widely applicable in linear algebra, analysis), which leads to other advanced topics.
Wrong. There's more than 1.5 million primes up to 24,036,583 (the largest Mersenne exponent known), and only 41 of these are Mersenne exponents.
Read what I typed, then read what you typed.
If I were wrong, then most of the Mersenne numbers would be composite. You have suggested that most of the large prime numbers are not Mersenne numbers, which is an unrelated concept, and substantiates my original post.
Do you have reading comprehension problems? Or is it just logic that escapes you? If only 41 primes up to 24,036,583 correspond to exponents of Mersenne primes, then the remaining 1.5 million or so primes up to 24,036,583 correspond to exponents of, you guessed it, Mersenne composites. I'd say that a compositeness ratio of 99.997% would indicate that `most' Mersenne numbers are composite.
I can only suggest you to heed your own advice.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
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.
Not taking your geek card, but you made the Bill Gates mistake, the numbers public key cryptographers are interested in are very large numbers with only two prime factors (besides the number and 1). I've never known anyone who couldn't factor even the largest prime numbers. : )
Worth knowing, yes. It does, however, stem directly from what primacy means.
Basic logic:
for some number, it is either prime or a product of two numbers
those numbers are either prime or a product of numbers
those numbers are either prime or a product of numbers...
and so on. Until all the numbers being multiplied are prime, they can always be factored into numbers that can be factored further (which meet the same criteria) or are prime.
Since primes are integers that cannot be factored, they are clearly going to be the ones left.
Well, depending on the architecture and the languages, linked lists can be easy :)
http://en.wikipedia.org/wiki/VList
"In computer science, the VList is a persistent data structure designed by Phil Bagwell in 2002 that combines the fast indexing of arrays with the easy extension of cons-based (or singly-linked) linked lists.
Like arrays, VLists have constant-time lookup on average and are highly compact, requiring only O(log n) storage for pointers, allowing them to take advantage of locality of reference. Like singly-linked or cons-based lists, they are persistent, and elements can be added to or removed from the front in constant time. Length can also be found in O(log n) time."
"The underlying structure of a VList can be seen as a singly-linked list of arrays whose sizes decrease geometrically; in its simplest form, the first contains the first half of the elements in the list, the next the first half of the remainder, and so on."
For some reason, the article affirms that the VList is immutable.
Try Corewar @ www.koth.org - rec.games.corewar
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
Prime numbers are used in public key encryption. This type of encryption relies on having a function that is easy to generate, but very difficult to reverse. Factorization of large numbers is exactly the function that is used in practice: the prime factors of a large number can easily be multiplied together to get an even larger number, but getting those prime factors back from the giant number is hard. In fact, as the giant number size increases linearly, the time to calculate the factors increases exponentially (using the best known algorithms).
On my computer, generating primes from 2 to 2^32 takes a third of the time to unbzip2 the same list.
check this one out:
http://cvs.sourceforge.net/viewcvs.py/buddy/bud
(there are zillions more, but this page was the one that i had in memory)
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
Throughout history, mathematicians have been fascinated with prime numbers - the sheer concept of indivisibility is one aspect (I mean, here they have numbers of infinite possible size that cannot ever be taken down into smaller whole units), and at the same time, these primes are the building blocks of all other numbers. Many great mathematicians have talked of prime numbers and developed more theories on them. Euclid proved there was an infinite number of prime numbers (basically showing that given any number of prime numbers, he could create a bigger prime number, or a number who had as a factor a prime number not included in this n). Riemann had his famous zeta function about the distribution of primes. We've named a great piece of beef after them (ok, not really, but I couldn't help the corny joke). Long story short, prime numbers seem fascinating (at least to me) because they are the building blocks, they are indivisible, and they seem to appear at random (that is, unless we can prove the Riemann Hypothesis) :-) That said, I concede prime numbers hold very little interesting value to many of those who find math too blah (the distribution of prime numbers mystery is hardly the mystery of the fate of Atlantis!)
Yeah, all those people seem to be under the delusion that one is prime... The number one is neither prime nor composite though (you'd think the mathematician in the joke would know that).
Actually, 1 not being a prime is more of a consensus than a mathematical fact.
Primes could be defined so that 1 is also a prime, it's just that way too many theorems we have these days would need to be refined to deal with 1 properly (starting with the fundamental theorem of arithmetics). Which is almost the same as to say, things are easier when 1 is not regarded a prime. But that doesn't imply that 1 is not a prime.
One could argue that it would be more practical if a positive interger would either be a composite or a prime. Because positive integers now split into three classes: Primes, composites and 1. Meaning that negating prime theorems for composites require special handling with 1.
Now, I wouldn't go telling anyone that 1 is a prime. But I'd be lieing if tried to claim that I remember to include it as an option when I'm assuming a number to be a prime when I've discovered that it's not a composite. Moreover, I must admit that, deep down, I do think of it as prime. It's just that the consensus is to leave it out of the equations, just like when we hop from N to Z+, to make things a little bit easier.
1 Earth is warming, 2 It's us, 3 it's royally bad, 4 we need to take action NOW
It appears you may be reinventing The Wheel. (I always wanted to say that, sorry...) That article discusses using the wheel for factorization, but it can also be used for compact storage of primes in a bit array. For example, a bitmap corresponding to only odd numbers would be a "wheel size" of two. If you also drop every bit divisible by three, you have a "wheel size" of six.
Surf around that site (http://primepages.org/), there's lots of good info there.
Tag lost or not installed.
By the prime number theorem, the probability that a given 7-digit number is prime is about 1/ln(10^8), which is roughly 5%. So the probability that two randomly picked numbers is prime is about 0.25%.