Glad I actually read the article because I never would have known this:
"The official discovery date is the day a human took note of the result. This is in keeping with tradition as M4253 is considered never to have been the largest known prime number because Hurwitz in 1961 read his computer printout backwards and saw M4423 was prime seconds before seeing that M4253 was also prime."
Also "Dr. Cooper's computer reported the prime in GIMPS on September 17, 2015 but it remained unnoticed until routine maintenance data-mined it."
I'd have thought that BIG FLASHING LIGHTS would go off if a prime were reported. Maybe with CELEBRATORY KLAXONS.
As long as you are talking about mathematical aliens, as in mathematical objects that are so different from every other know mathematical object currently recognized in the corpus of Math.
If you further claim that this objects are, like, sentient... I guess this would be too Pythagorean for my tastes. ;)
Big numbers are fun. Here's some stupid stuff I thought of while reading about this.
The number is 2^74,207,281 - 1. Naively stored like a normal integer in memory, that's roughly 75 MB of RAM just to store the number. Compare that to your 64-bit time_t and imagine how long a duration of time could be represented by such a large number. Stored on 3.5" floppy disks for some reason, that's roughly 50 disks just to store the number.
Edit: Duh, bits, not bytes. I leave my mistake here for posterity.
gzipped it's a 9043 byte file when the source is the number expressed exactly as bits. gzipping that 9043 byte file yields a 129 byte file, which gzip can't compress any further. Base64 of the file:
M49 (for the 49th mersenne prime) fits in 2 bytes! Or even better just 49! 6 bits! Assuming your decompression algorithm is optimized for mersenne primes. :)
No, the number 5 is prime, yet in binary it is 101. The new prime number could have many zeroes interspersed with ones, so you don't know how many 1 digits it has.
EDIT: I have realized my mistake in the representation of 2's complement. However, I will leave this here for posterity.
Turns out run-length encoding it is more or less what you get if you store it as 2^74,207,281 - 1. I imagine this probably is how they store it actually; note that 2^n == 1<<n so you can just store the exponent and complement (74 207 281, 1) and then do normal two's complement math.
If you're talking about storing it in computer memory during calculation, then no, it's written out. The fast MOD operation you list isn't used, it's an FFT using a weight factor that automatically does the mod operation while squaring a number. You start with S[0] = 4, S[i+1] = Si^2 - 2 MOD N. If S[N-2] = 0 then the number is prime.
So it's 74,207,279 squares using FFT, each likely more than 75 MiB since there will likely be lots of leading zeros (we're probably close to the maximum number of digits using double precision, round off errors dominate unless you start using really small bases and even greater-length FFTs).
That's not counting the two or three compositeness tests that GIMPS uses before starting the Lucas-Lehmer test to prove primality.
For several years I've been working on a program to test for primality of the Generalized Fermat numbers, using NTT instead of FFT. NTT is exact (integer math), and the GFNs likely are more "dense" with primes than the Mersenne Numbers. And they also have a faster form to test, although the primality test has a 50% chance of false negative, so you have to run it a few times to be sure a number isn't prime. That's where Mersenne Numbers are easier to test.
I remember those. They either came with a loupe, or mentioned explicitly to the buyer that you needed one to see individual numbers. Always wanted to get one. It looked like an all grey poster if you didn't know what it was.
75 MB compresess neatly to under 12 bytes, which I say because the string "2^74207281-1" is totally unambiguous (Wolfram Alpha will evaluate it for you no questions asked, no guesswork, though obviously it only approximates the output). So the Kolmogorov complexity of the 75 MB is 96 bits or less.
It is far too many bits to be used for time representation. 512 bits is all that needed to store every planck time (10^-44 seconds) since the big bang until the heat death of the universe (10^100 years).
Sure, that's fine if all you want is to measure the time from the big bang until the last matter in the universe has evaporated into photon soup. But what if you want the time until those photons are evenly distributed? An article I read a while back estimated that duration as 10^10^78 years, which is absolutely mindboggling and remains the largest number I have ever seen with a real-world physical application.
(It may never happen, though; according to Wikipedia, random quantum fluctuations may be sufficient to produce another Big Bang in a mere 10^10^56 years.)
That makes sense for durations, but a time_t is actually a timestamp. A proper time can have the same units as a duration, but is only useful in conjunction with information about the trajectory of the clock measuring the time. If space is continuous, the amount of information to specify the trajectory is limited only by the capabilities of the measurement apparatus. Of course, for all we know at this point spacetime is quantized; so we should probably hold off on standardizing the time format to end all time formats.
Or you create a new compression scheme just for Mersenne prime numbers where store the exponent. You'll be able to compress the entire number into just 32 bits for several decades at least!
Since the exponent is prime you should be able to compress it further than that, by simply noting n is the kth prime number. Supposedly as n goes to infinity the probability that n is prime drops to zero, so that should compress handily.
Decompressing it, on the other hand, would be pretty slow however. Are primality tests O(n) or O(nlogn)? That puts decompression up to O(n^2) without a pre computed lookup table.
If you were abducted by aliens, and had memorized that number, you could possibly trade it for wealth in their society. If they hadn't discovered it yet!
Apparently a $3,000 GIMPS research discovery award. What's the practical utility of knowledge of a prime, especially considering that upon announcement it's immediately disseminated?
It's a very large prime number which has a very convenient representation, which makes it useful. You could use it in a Mersenne Twister RNG, for instance.
Interestingly, if the alien's memorized number was significantly larger (e.x. tens of billions of digits) we would not be able to verify it. It took three and a half days to verify the correctness of M74207281 on two 18-core Xeon servers, and with speed increases in computing slowing down it may be a very long time before we are able to verify a number that large.
So, nothing. The alien could say "Oh yeah, we have 2^34240923842043983204982-1" and they could be absolutely correct but there's nothing we could do to know.
Or, if their number was big but not that big, it might be able to be verified in, say, a year, in which case it might win the EFF's prize and could possibly get some other sort of prize money. So, $150k + some undefined amount.
That's how you solve all problems of this form. For any a and b, a^n mod b eventually becomes periodic as n grows. It's easy to prove because there's only a finite number of possible remainders mod b. As an exercise, calculate 3^1000000 mod 7.
Write out the number in decimal, add the digits together: if the result is larger than a single digit, repeat. When you have a single digit, if it is 3, 6 or 9, the number is divisible by 3.
That's the divisibility check for 3, yes, but I am pretty sure fdej didn't write that number out in decimal. The proof doesn't work with exponents. You'd have to represent the number in base 10 for digit summing to work.
To check, 2^6-1=63 is divisible by three (it might work), but 2^9-1 has a sum of 12 and a value of 511, which is not divisible by three (it's 170 * 3 = 510 + 1).
I'm curious to understand the significance of finding the largest known prime numbers. It seems that some people get pretty excited but I'm not sure if it's just purely academic or there's some useful applications I'm unaware of. Can anyone enlighten me?
Prime numbers are tricky things. They are one of the most fundamental parts of our numerical systems, but they're difficult to predict.
You would kind of expect that something so elementary should be easily predictable, or follow a pattern. But while we've found some similarities (like the mersenne primes) there's still a kind of nagging feeling that there should be a more basic way to enumerate prime numbers than guess and check.
We've learned some simple things about them, such as the existence of Mersenne primes, or ideas on the probability of any given number being prime being inversely proportional to its logarithm.
But I think the biggest thing is that it's a puzzle. But a puzzle that bothers us because it seems like it should be easy to solve, but it's not.
Finding larger prime numbers tells us more about them. It lets us see other parts of patterns. Patterns that might lead to some insight on how to predict if a number is a prime, or how to factor large numbers. This might have an impact on cryptography for instance.
But finding this number doesn't solve a problem, it adds to a body of knowledge. It fills in a bit of the puzzle. In the end the hope is that we learn something about the puzzle, or at the least, learn why we can never learn something about the puzzle.
"The EFF awards are about cooperation," said John Gilmore, EFF co-founder and project leader for the awards. "Prime numbers are important in mathematics and encryption, but the real message is that many other problems can be solved by similar methods."
Finding these prime numbers will be no simple task, given today's computational power. It has taken mathematicians years to uncover and confirm new largest known primes. However, the computer industry produces millions of new computers each year, which sit idle much of the time, running screen savers or waiting for the user to do something. EFF is encouraging people to pool their computing power over the Internet, to work together to share this massive resource. In the process, EFF hopes to inspire experts to apply collaborative computing to large problems, and thereby foster new technologies and opportunities for everyone.
> However, the computer industry produces millions of new computers each year, which sit idle much of the time, running screen savers or waiting for the user to do something.
Considering how much more electricity a running computer uses versus an idle one and how much faster consumer CPUs degrade under load this definitely seems like a huge waste of resources for something that has little, if any, utility.
I used to run prime95 on all of my machines, back when power management (especially on desktops) was virtually nonexistent. Obviously, with the power management features we have now, an idle CPU (especially outside of a hosting environment) is not considered wasteful.
This sort of thing is comparable to sending humans to the Moon. In and of itself, there's not much of a point to it; but the technology you develop to get there has a tendency to become useful in other, perhaps more useful, areas.
In the case of the Mersenne prime hunt, you need the fastest integer multiplication algorithms (and concrete implementations) you can. Fast integer multiplication is a big part of several useful number-theoretic algorithms. An interesting (to me) application is, for example, to check whether a number is only divisible by small primes. This is an integral part of the most efficient integer factorization algorithms known, and one way to do it is with a product tree followed by a remainder tree [1]. This would be unacceptably slow without quasilinear-time multiplication algorithms.
One of the key features of pure mathematics is that we come up with results just to have sitting around, on the off chance they ever become useful. And often they do, much later on. It’s a gift to the future.
In 1940, Hardy used the theory of numbers as an example of a profoundly and permanently useless discipline in A Mathematicians Apology[1]. The fact that number theory is the basis for modern cryptography gives the lie to this sentiment.
The fact is that we don't know whether the search for Mersenne primes, or any other mathematical endeavour, will reveal anything useful, but given the depth of interconnection between different branches of mathematics and the usefulness of some of those branches, it doesn't seem plausible that we won't find useful things.
Although Hardy turned out to be wrong about number theory and its applications, his arguments for the intrinsic value of the study of mathematics in the absence of any real utility stand as well.
And of course, as another commenter has pointed out, making computers do things like this is a great way to develop phenomenally fast and useful algorithms.
Finally, the project found a bug in Intel CPUs[2], which is kind of neat...
It's similar to Barry Bonds hitting the most home runs. It serves the world nothing but lots of exercise for Barry, but it's an achievement that everyone can feel proud about. In addition, the GIMPS project has contributed to an efficient FFT and to distributed computing research.
I had to find out what a Mersenne number was again (vaguely remember but forgot) and I was shocked to find this problem in mathematics:
"It is not known whether or not there is an odd perfect number, but if there is one it is big! This is probably the oldest unsolved problem in all of mathematics." [1]
They use the Lucas–Lehmer primality test [0], along with trial factoring candidate numbers up to a given bit depth to sift out some composites from the prime candidates quicker than a full LL test.
They use special form primes (the big primes are all n+1 or n-1 forms, with n being easy to factor).
If a Mersenne Number is prime, then the exponent must also be prime (74,207,281 is also prime). That cuts down on a lot of processing time.
Also, all factors of a Mersenne Number, if it's composite, are of the form 2nk + 1, where the Mersenne number is written 2^n - 1. That also helps factor it. I generated a huge list of prime number indices and did some tests on them a couple of years ago. 25% of the Mersenne numbers have 2*n + 1 as a factor. That's even less computation time to find a large prime.
I believe they actually have very optimized algorithms to test for primality [0], which not necessarily involve diving by every possible number.
There are simple tests and there are more complex ones, that use probabilities and other workarounds to avoid having to divide by every possible number.
Good question, no, no idea but of those two fftw would appear to have the edge so if you're going to compare do it with that one. I do know the fftw guys benchmarked an older version of it but I can't find the results (there used to be a bunch of graphs showing the relative performance of all those ffts listed).
It should be fairly easy to figure this out though, the benchmark code is public and if fft sizes you are interested in are known you could make a very precise comparison.
One warning about the mersenne fft code, it is not the most readable one on account of all the optimizations, but if all you're interested in is a drop-in library then it might suit your needs, especially if the size fft you're after is one that has already been optimized to the hilt by the mersenne project people. If you find you need to customize it then you're probably better off with a more universal implementation, even at the expense of some cycles.
I have a stupid question that will reveal how I know nothing about cryptography. I understand that large primes are somehow important for some types of cryptography. How are there not just databases of large primes that make breaking the types of cryptography that rely on large primes trivial?
There are too many. Not just more than could fit in every database on Earth. More than could fit on every database if every star in the sky had an Earth, each with as many databases as there are on Earth.
This is nothing specific to cryptography or prime numbers. Fun fact: if you shuffle a deck of cards correctly, it's almost certain that no one in history has ever had a deck in the exact same order. https://www.math.hmc.edu/funfacts/ffiles/10002.4-6.shtml
I understand that there's a huge number of primes, but surely the primes being used to generate keys or whatever process they're involved in are "known" primes, right? It's not as if when I try to encrypt something my machine is going to search for a new prime number that hopefully won't get guessed.
Long prime numbers are used for RSA keys. You only generate RSA keys when creating a new identity (webserver certificate, client certificate, SSH key, etc). Then, you do search for "a new prime number that hopefully won't get guessed". It can take from a few seconds to several minutes, depending on the hardware and the desired key length.
The usual approach is to take a random odd number of desired length and then have a probabilistic primality test (much faster than what would be needed for a formal proof). Several attacks rely on bad entropy or bad pseudo random number generators (PRNG) to guess what prime was selected.
They represent the largest known primes, as the special case 2^n-1 allows us to verify their primeness using a method much more efficient than checking all potential factors.
So to answer your question, if there's ever a need for ridiculously large numbers that are known to be prime this is how we'll fill it.
Short of that need, it's still fun as a mathematical world record!
"The official discovery date is the day a human took note of the result. This is in keeping with tradition as M4253 is considered never to have been the largest known prime number because Hurwitz in 1961 read his computer printout backwards and saw M4423 was prime seconds before seeing that M4253 was also prime."