I can swear something like 20+ years ago I found a new one too, but I didn’t realize the importance of it. I had just downloaded GIMPS and I was just messing around with it, and when I saw the message I thought “ok, cool!” and proceeded to turn it off.
If this happened the way you remember, it's really unfortunate, but it wouldn't have stopped the prime in question from being discovered, because GIMPS always at least eventually gives out numbers to multiple people to check, and doesn't mark Mersenne numbers as checked until a computer actively reports that they were checked.
However, your name could have ended up on that Wikipedia list as a discoverer. :-)
> because GIMPS always at least eventually gives out numbers to multiple people to check
For the 40th Mersenne prime, 2²⁰⁹⁹⁶⁰¹¹ − 1, for example, the status page on mersenne.org seems to suggest only a single check (and a handful of later NF checks later), but maybe follow-up proofs and proof certifications and reruns are omitted? https://www.mersenne.org/report_exponent/?exp_lo=20996011&fu...
Also, when you sign up, you're asked to provide an email address in case they want to get in touch with you, so even if OP didn't themselves do so, I imagine they would include their work just the same?
> However, your name could have ended up on that Wikipedia list as a discoverer. :-)
Along the same lines, since each (potential) prime is being worked on by many computers, some looking for factors, some running the Fermat test, some running proof certification work, who gets the "discoverer" title; just the person who ran the PRP test? If so, seems fair enough, since that's where most of the computational budget ends up, but on the other hand, it seems like that would disincentivize running anything but PRP tests. But maybe the people involved are just in it for the mission (or the GHz day leaderboards).
Interesting that all the primes since 2001 have been discovered by Intel processors (at least those where the processor was recorded). How’s that for marketing?
If bitcoin used a facet of primality in its Proof-of-Work, that would nearly needlessly gloating.
But it doesn't, and unfortunately even worse, it wasn't ASIC-resistant, which had second-order effects that Intel could had actually taken advantage of if they werent sleeping from being too comfortable.
This reminded me that I used to leave my computer running Folding@home or similar projects around 2010-2011. Not sure if it ever contributed to anything. If only I had known to run a Bitcoin miner instead!
Back in 2009-2010 I was responsible for deploying 8-16 core servers to customers to run large databases and ERPs. I had the idea of doing some burn in testing to stress the components for around a week for each server. Back then I was aware of bitcoin but also SETI@home. Obviously I chose the second option as I believed it was probable my a better choice for humans kind. It obviously was, but bitcoin mining would have been a better one for me.
I remember some rough calculations suggested I needed to upgrade from agp to pcie to make bitcoin mining worth it financially. I went with boinc instead.
Thats it (afaik), and it could be for the usual, dismissive reasons, but its easy to hand-waive the "make primality a part of the work" part but it also comes down to the properties of the work that require it to be useful:
the difficulty of the work must be adjustable,
the difficulty/reward ratio must scale to the polynomial of users/work-rate to avoid sybil/"51% (31%)" attacks, and dissuade volatility during transitions
must be easily verifiable,
Primecoin uses Cunningham Chain primes - basically sequences of primes where 2x+1 is prime.
They are marginally useful with other applications on the horizon.
I could see adjusting the arbitrary rule-set - similar to the varying rulesets of cellular automata, like Conways - to further Number Theory/Game Theory/Swarm Economics at a general interdisciplinary level to be the most potentially rewarding, covering a larger swath of unknown unknowns.
My favorite “Practical POW” remains komoglorav complexity computation. The reward would likely scale with the runtime needed to verify a complexity, but there’s plenty of room for subtleties in the implementation. (for instance what happens when you prove a prior established complexity wrong?)
>(for instance what happens when you prove a prior established complexity wrong?)
what do you mean? you run their wallets, pun intended!
No stakes, no steaks!
But it does seem interesting - counterintuitive really, but a "Busy Beaver" / proof of work verifying mechanism enumerating inputs/instructions/outputs randomly (or whatever the nodes think they know best at ) while rewarding (only? why not top 3?) the shortest, most efficient block...could be tweaked to crunch ETH contracts like gas, brute-force fuzz-test legacy unsafe sourcecode...literally a foundation for further distributed computation.
There are languages like it - Dennis and his Bubblegum - that have generative, selective, and compressive patterns interned already.
Gapcoin (finding large gaps between successive primes)
Riecoin (finding maximally dense prime clusters of size 6)
Nexus (finding almost-dense clusters with a maximum spacing between successive primes)
As an aside, picking a mathematically interesting and intricate proof of work function is probably a bad idea, because someone like me will come along and optimize the miner and mine privately at a large profit margin, as I did with two of these coins.
The work in a PoW algorithm has to be otherwise useless in order for it to most effectively deter abuse, or else you'd still be able to get value out of failed attack attempts
I'd believe it. Many years ago when I was around 10 years old and not understanding the concept of probability properly, I decided I had come up with a way to enumerate the lottery numbers and come up with a reasonably sized set of numbers to place bets for. I proceeded to write 9 pages of numbers for my father to place bets for. It is a 6/49 lottery so 6 balls are drawn from a set of 49 and you need to get all of them right to get the jackpot.
It would have cost a little under 95$ to have played all my numbers (for a jackpot around $1.5M) I gave him however it would have taken a lot of effort to manually enter them. My father just does one page because it is silly. The numbers are silly, everything about this is silly. I completely understand in hindsight. But it turned out page 7 had the winning combination.
If the balls were improperly weighted at the lottery commission, then maybe you'd have unwittingly discovered the bias in the game. That's certainly possible.
I thought this was about GIMP at first, the GNU Image Manipulation Program. Like did they hide a prime number check into the brush strokes algorithm so users would become pseudorandom generators whenever they made art...? And you just happened to draw the right thing that also happened to be a prime?
I remember the faucet giving 5 BTC to play with. I still have my wallet history from those days, with transactions of multiple millions (today) in BTC between wallets and friends.
> I had just downloaded GIMPS and I was just messing around with it, and when I saw the message I thought “ok, cool!” and proceeded to turn it off.
GIMPS would run for weeks or months first. You wouldn’t have seen anything if you had just downloaded it and were messing around. As I recall, you had to do some work to get it running at boot automatically.
Do you have any slightest idea about the exponent, including how many digits in the exponent? I assume you had no account (otherwise there should have been some logs for that).
I use to run Mersenne Prime Search (GIMPS), but now all I have is laptops. It runs to hot on the Laptops I have :(
Will need to play with throttling some more.
Edit: found mprime (mprime-bin-24.14) is available in NetBSD pkgsrc. But this uses 32 bit linux emulation to execute, I have been trying to avoid it, but may try it.
I think there's actually a fair number of them, but more would be nice. Lots of protein folding ones, and there used to be a weather/climate related couple.
Awesome. I have been recommending in my organization, 24 Hrs. Prime95 Stress Test as part of acceptance protocol for all new servers ! Happy to see it find another record Mersenne Prime.
Given this contest can presumably go on infinitely long, what is the ultimate point of the contest? Is there some kind of theoretical or practical benefit to discovering a new Mersenne prime?
The EFF Cooperative Computing Awards, which pay out money for (four specific sizes of) prime records, were meant to show off how the Internet is useful for letting people who don't even know each other work together to solve problems. They were established back in 1998, when people in general were much less familiar with the Internet and its impact. That specific contest isn't set up to go on forever, as it ends when a billion-digit prime is discovered.
The search for different kinds of mathematical objects sometimes has applications and sometimes doesn't. For example, apparently the search for Golomb rulers (another distributed computing project) has some conceivable applications.
There's a misconception (that I heard dozens or hundreds of times when I was running the Cooperative Computing Awards at EFF) that discovering world record primes is useful to cryptography. In fact, it has no direct application because all of the primes used in number-theoretic algorithms like RSA and classic Diffie-Hellman are dramatically smaller than world-record sizes, and can be generated on an ordinary PC in seconds. (Try "openssl prime -generate -bits 2048" at your command line!)
(There is a wild paper from 2017 called "Post-quantum RSA" arguing that we could in principle just scale up RSA keys for post-quantum security, but that paper uses multiprime RSA moduli composed of large numbers of 4096-bit primes, instead of just the traditional two primes, so even that approach doesn't require individual primes that are especially large or hard-to-find by computer standards.)
We have apparently learned a bit about number theory and algorithms as a result of research done by the GIMPS project and its collaborators about how to optimize some of the arithmetic in the GIMPS client. I guess that's the equivalent of the claim that the space program produced various spin-off technologies while pursuing space exploration.
In general, since there are infinitely many primes, there's no reason that humanity can't keep looking for larger and larger ones indefinitely. Likewise for many other searches, both for objects which are known to be infinitely numerous and objects which may or may not have a largest example. Mostly this kind of activity has a "because it's there" flavor to it.
Research mathematicians are mostly not that excited about this activity, because it isn't generating more understanding or hypotheses about mathematical structure. They're usually more excited about insights that reveal or hint at new patterns or structure, which searching for large primes doesn't really do (most of the work is mechanical, performed by computers, and the outputs aren't very surprising or suggestive in a mathematical sense).
I've hoped that publicity about discoveries like record primes might get more young people interested in mathematics (and maybe about topics like number theory and discrete math that they might not be encountering in school). I got kind of a sad view of this because people were constantly writing to me asking for monetary rewards for their inevitably-mistaken-or-confused "discoveries", but I'd like to think that there are also people out there who got curious about what we do and don't know about primes. A good place to start with that is the Prime Pages
And wasn't that paper just poking fun at people who still used something as outdated as RSA as the default public key crypto primitive in the 2010s by extrapolating their position to its logical extreme?
I think there was an intended humor element there, particularly since some of those people were also working on new post-quantum primitives, but they also "committed to the bit" and did the research for real.
Do we expect to learn something interesting from any given new Mersenne prime discovered? Don't we kinda have enough so that if we are going to discover something interesting by analyzing them, we can do that with the ones we already know about?
I'm not an SME but I would imagine that if there's some sort of very large scale pattern in Mersenne primes then finding that might lead to the discovery of some currently unknown emergent property. Of course this argument is likely unfalsifiable, as it can scale infinitely if there's an infinite amount of them, though we don't even know whether they are a finite set or not.
Sure, I'm not against GIMPS or anything, I'm just a bit doubtful that finding a few more Mersenne primes could be the key to unlocking some secret pattern in the primes is all
I didn't claim there are an infinite number of Mersenne primes. I said the contest could presumably go on infinitely long. The latter doesn't require the former. It's only predicated on us lacking proofs about how many there must be.
The traditional proof that there are an infinite number of primes relies on unique prime factorisation- i.e for any number, n, there is a unique set of primes p1, p2, p3, … etc. where p1 * p2 * p3 * … = n
For instance 88 = 2 * 2 * 2 * 11, 42 = 2 * 3 * 7
It’s worth reading the proof if you haven’t - it’s comprehensible with high school maths.
No such property exists for Mersenne primes, so we can’t trivially extend it. Many proofs of the properties of prime numbers are difficult because they, by definition, actively resist patterns.
the idea of a deep-nation-state-cold-war psyop campaign bluffing and escalating math proofs is so goddamn hilarious, apt, and ironic it would be almost better than the mistake of pissing off the Aliens by offending them with math homework.
"Shizuo Kakutani joked that the problem [Collatz conjecture] was a Cold War invention of the Russians meant to slow the progress of mathematics in the West."
This still suffers from the MitM / Two Generals Problem, and is existentially problematic if they also demand the simple, reasonable sum of the first BB(17) numbers modulo Grahams number, within 14 business local parsec-years.
Their spam filter may be an annoying ping acknowledgement, a directed gamma ray beam from soft gamma repeater, just to irradiate their own hoax-doers suspects.
Because the EFF Cooperative Computing Awards for the first discovery of large enough prime numbers are still active. Publishing the probable prime in advance would risk someone verifying faster than GIMPS.
I used to run the Cooperative Computing Awards, and I don't think this is the reason in this case.
The most recent award was given out in 2009 for a prime over 10,000,000 digits in length. The next available award is for a prime over 100,000,000 digits in length.
But the most recent discovery by GIMPS prior to the current discovery was a prime with length only 24,862,048.
The primes they've found have been getting longer by only single millions of digits every several years, so it's not very plausible that this discovery would qualify for a monetary award.
I suspect they just don't want to announce a number before it's verified on general scientific-integrity grounds.
GIMPS currently searches for exponents up to 999,999,999, corresponding to 301,029,996 decimal digits. We don't really know much about the exact distribution of Mersenne primes so it is possible that a new discovery was from much higher ranges and thus eligible for prizes.
But yeah, they'd probably embargoed even without any potential monetary prizes because it's wise to do so in general ;-)
Sure, but all actual historical discoveries of Mersenne primes since the 1980s have been in strictly increasing size order, with no missed primes in between found in retrospect, and the successful exponents have increased gradually rather than sharply in size. It would really buck the trend to an extreme degree if the new successful exponent were 5× as large rather than something like 1.05× as large as the previous record.
I want to make an analogy to sports records, but the analogy will obviously be imperfect because the limits of human physiology are better understood in some ways than the behavior of Mersenne primes and perfect numbers. But it might be like if we heard that the marathon record had been beaten and then it turned out that the new record was something like 1:30:00 instead of something like 2:00:00. Obviously the exact value of the new record is totally unpredictable, but the best bet is that something like long-term trend lines will continue to be followed, rather than abruptly radically changed by multiple orders of magnitude.
M43112609 (2008-08) was discovered prior to M42643801 (2009-06), so that order is not really strict. I agree that there is a human tendency to test smaller primes (thus faster to verify) first, but it should be also noted that every single Mersenne number smaller than M124399361 has been already tested at least once by someone even though that limit would be way higher than what we have for primes. There are also some groups of people that specifically look for prime numbers that are barely enough to be 100,000,000+ decimal digits [1]. Given we didn't see any new Mersenne prime for many years, new prime from a random range seems much more likely than ever.
[1] See https://www.mersenne.org/primenet/ and scroll down to the starting exponent of 332,000,000. There would be an unusually large number of assigned LL/PRP tasks around this range. In fact, this holds for virtually all available PrimeNet statuses in the Wayback machine!
Any% (Anything goes to get to the "end") Video game speedruns may be ideal - a shortcut can always be found, used by everyone to quickly become zero sum + 1, then the equilibrium re-approaches optimization; but on average, gets harder and harder, as the shortcuts take skill/power/time. It also is hard to do, and easy(ish) to verify.
For linear things that hardly have any variance, you can look at longest lifespans of humans. Notably; where living 18 months longer than the next person
statistically makes it more likely that you are actually your own mother and lied.
How do you prove that you verified that a number is a prime?
If you want to prove that a number is not a prime you can show the factorization or that it breack the little theorem of Fermat with 367984321568, and everyone can check the refutation inmediately.
I don't know a similar method to show that you actualy verified the number is a prime.
These are sometimes infeasible for stupidly big numbers, but the Mersenne Primes have a specific structure that allows for simplification of the process.
That someone will totally count as the discoverer under the current rules [1], because it requires the deterministic primality proof for given number. It doesn't matter how much effort was taken to reach that candidate so far, even though it would be virtually impossible to find any new prime without that. I think the temporary embargo is fully justified for this reason.
(And I think it is technically possible to probe the reports to find what it was anyway, but it is not easy to find one at least for me. If you are really looking for that, look for the P-PRP result type.)
Any probabilistic primality test will work, but GIMPS currently uses the first-time Fermat probable prime test with a very robust certificate [1] to filter almost all non-primes in advance.
Are there statistics on the scale of compute available to GIMPS for this search? Is there any evidence that by crowdsourcing the clients, we are searching faster than, eg, a dedicated cluster financed by a government or a corporation? What is the impact of GIMPS as a distributed problem solving tool? Like, if there was a practical application, how much money would it take to exceed GIMPS throughput, that curious people provide for free?
I’d like it to be astronomical, but given the niche of this, and the low cost of cloud compute, the answer is predicable depressing, like, “$50k/year in AWS costs would equal current GIMPS search throughput”
I used a random estimate online for computing cost which had 5.6e17 Flops per dollar on A100s gives about a dollar every 4.4 seconds or ~$7 million per year.
Sadly, I do not vouch for the correctness of any part of this, though I did try.
So I prefer to shorten the definition to "A prime of the form 2ⁿ-1". It’s bloody useful that n has to be prime though: makes searching that much faster.
And we look for Mersenne primes, AFAIU, mainly because Mersenne numbers are more likely to be prime than other numbers, so it's easier to find big primes that way.
I always wondered if we could parallelize a prime test on GPU. That would give us a Datacenter level compute and really help us scale, but it might be too hard to do.
I can swear something like 20+ years ago I found a new one too, but I didn’t realize the importance of it. I had just downloaded GIMPS and I was just messing around with it, and when I saw the message I thought “ok, cool!” and proceeded to turn it off.
If it was literally around "20+ years ago", like 2004 or slightly before, it might have been M40 or M41.
https://en.wikipedia.org/wiki/List_of_Mersenne_primes_and_pe...
If this happened the way you remember, it's really unfortunate, but it wouldn't have stopped the prime in question from being discovered, because GIMPS always at least eventually gives out numbers to multiple people to check, and doesn't mark Mersenne numbers as checked until a computer actively reports that they were checked.
However, your name could have ended up on that Wikipedia list as a discoverer. :-)
I'm curious how this is organized.
> because GIMPS always at least eventually gives out numbers to multiple people to check
For the 40th Mersenne prime, 2²⁰⁹⁹⁶⁰¹¹ − 1, for example, the status page on mersenne.org seems to suggest only a single check (and a handful of later NF checks later), but maybe follow-up proofs and proof certifications and reruns are omitted? https://www.mersenne.org/report_exponent/?exp_lo=20996011&fu...
Also, when you sign up, you're asked to provide an email address in case they want to get in touch with you, so even if OP didn't themselves do so, I imagine they would include their work just the same?
> However, your name could have ended up on that Wikipedia list as a discoverer. :-)
Along the same lines, since each (potential) prime is being worked on by many computers, some looking for factors, some running the Fermat test, some running proof certification work, who gets the "discoverer" title; just the person who ran the PRP test? If so, seems fair enough, since that's where most of the computational budget ends up, but on the other hand, it seems like that would disincentivize running anything but PRP tests. But maybe the people involved are just in it for the mission (or the GHz day leaderboards).
Interesting that all the primes since 2001 have been discovered by Intel processors (at least those where the processor was recorded). How’s that for marketing?
If bitcoin used a facet of primality in its Proof-of-Work, that would nearly needlessly gloating.
But it doesn't, and unfortunately even worse, it wasn't ASIC-resistant, which had second-order effects that Intel could had actually taken advantage of if they werent sleeping from being too comfortable.
This reminded me that I used to leave my computer running Folding@home or similar projects around 2010-2011. Not sure if it ever contributed to anything. If only I had known to run a Bitcoin miner instead!
Back in 2009-2010 I was responsible for deploying 8-16 core servers to customers to run large databases and ERPs. I had the idea of doing some burn in testing to stress the components for around a week for each server. Back then I was aware of bitcoin but also SETI@home. Obviously I chose the second option as I believed it was probable my a better choice for humans kind. It obviously was, but bitcoin mining would have been a better one for me.
I remember some rough calculations suggested I needed to upgrade from agp to pcie to make bitcoin mining worth it financially. I went with boinc instead.
I remember calculating that the 0.08 btc that I was mining per day on my desktop wasn't worth the electricity.
That's exactly how Bitcoin is designed to autobalance. It's only worthwhile if you believe demand will increase in future.
Maxim 19: The world is richer when you turn enemies into friends, but that's not the same as you being richer.
I ran the SETI software as well. Was not Bitcoin mining....
I suspect neither your or I though have ever had to turn over a landfill looking for a hard drive. So there's that anyway.
Is there a good POW mechanism that would test primes?
I found this but curious what else exists! https://en.wikipedia.org/wiki/Primecoin
Thats it (afaik), and it could be for the usual, dismissive reasons, but its easy to hand-waive the "make primality a part of the work" part but it also comes down to the properties of the work that require it to be useful:
the difficulty of the work must be adjustable,
the difficulty/reward ratio must scale to the polynomial of users/work-rate to avoid sybil/"51% (31%)" attacks, and dissuade volatility during transitions
must be easily verifiable,
Primecoin uses Cunningham Chain primes - basically sequences of primes where 2x+1 is prime.
They are marginally useful with other applications on the horizon.
I could see adjusting the arbitrary rule-set - similar to the varying rulesets of cellular automata, like Conways - to further Number Theory/Game Theory/Swarm Economics at a general interdisciplinary level to be the most potentially rewarding, covering a larger swath of unknown unknowns.
You forgot one important property: it must commit to the new block(header).
My favorite “Practical POW” remains komoglorav complexity computation. The reward would likely scale with the runtime needed to verify a complexity, but there’s plenty of room for subtleties in the implementation. (for instance what happens when you prove a prior established complexity wrong?)
No stakes, no steaks!
But it does seem interesting - counterintuitive really, but a "Busy Beaver" / proof of work verifying mechanism enumerating inputs/instructions/outputs randomly (or whatever the nodes think they know best at ) while rewarding (only? why not top 3?) the shortest, most efficient block...could be tweaked to crunch ETH contracts like gas, brute-force fuzz-test legacy unsafe sourcecode...literally a foundation for further distributed computation.
There are languages like it - Dennis and his Bubblegum - that have generative, selective, and compressive patterns interned already.
https://esolangs.org/wiki/Bubblegum
Primecoin (Cunningham chains)
Gapcoin (finding large gaps between successive primes)
Riecoin (finding maximally dense prime clusters of size 6)
Nexus (finding almost-dense clusters with a maximum spacing between successive primes)
As an aside, picking a mathematically interesting and intricate proof of work function is probably a bad idea, because someone like me will come along and optimize the miner and mine privately at a large profit margin, as I did with two of these coins.
Don't forget:
Primemarkcoin
Perceptiongapcoin
Liecoin
epiplexiscoin
and of course, the every useful pyramidcoin and scamcoin.
There's also https://gapcoin.org/ for searching prime number gaps (mine the gap).
I knew I forgot something, thank you!
10 years!
There's also https://riecoin.xyz/ searching prime constellations.
What second order effect are you referring to? Stuff like manufacturing, or fab availability perhaps?
The work in a PoW algorithm has to be otherwise useless in order for it to most effectively deter abuse, or else you'd still be able to get value out of failed attack attempts
[dead]
I'd believe it. Many years ago when I was around 10 years old and not understanding the concept of probability properly, I decided I had come up with a way to enumerate the lottery numbers and come up with a reasonably sized set of numbers to place bets for. I proceeded to write 9 pages of numbers for my father to place bets for. It is a 6/49 lottery so 6 balls are drawn from a set of 49 and you need to get all of them right to get the jackpot.
It would have cost a little under 95$ to have played all my numbers (for a jackpot around $1.5M) I gave him however it would have taken a lot of effort to manually enter them. My father just does one page because it is silly. The numbers are silly, everything about this is silly. I completely understand in hindsight. But it turned out page 7 had the winning combination.
If the balls were improperly weighted at the lottery commission, then maybe you'd have unwittingly discovered the bias in the game. That's certainly possible.
I've seen that movie too
I'm not sure why your comment is currently downvoted, you're not claiming it was anything but random luck and it's a funny story. Thanks for sharing.
I thought this was about GIMP at first, the GNU Image Manipulation Program. Like did they hide a prime number check into the brush strokes algorithm so users would become pseudorandom generators whenever they made art...? And you just happened to draw the right thing that also happened to be a prime?
But nope, it's just a similar acronym! https://en.wikipedia.org/wiki/Great_Internet_Mersenne_Prime_...
I absolutely had the same thought progression
Hey at least you weren't one of those kids who ran into those online faucets that were giving bitcoins for free and didn't think too much about it.
I remember the faucet giving 5 BTC to play with. I still have my wallet history from those days, with transactions of multiple millions (today) in BTC between wallets and friends.
its like "the game" but you feel like you got stabbed by Hindsight herself
> I had just downloaded GIMPS and I was just messing around with it, and when I saw the message I thought “ok, cool!” and proceeded to turn it off.
GIMPS would run for weeks or months first. You wouldn’t have seen anything if you had just downloaded it and were messing around. As I recall, you had to do some work to get it running at boot automatically.
Does it take months to check one prime? Maybe the author got extremely lucky.
Do you have any slightest idea about the exponent, including how many digits in the exponent? I assume you had no account (otherwise there should have been some logs for that).
[dead]
Time for Bruce Schneier to change the combination to his luggage again
For anyone who didn't get the joke, this is a reference to
https://www.schneierfacts.com/facts/365
from the "Bruce Schneier Facts" series (which was inspired by the "Chuck Norris Facts").
Not 137? https://www.schneier.com/blog/archives/2005/06/picking_physi...
It’s not quite 137, though. The last digit needs to be oh so slightly off.
looking at the picture, I imagine it's like a zero day when you can "enter the drag-on'
(it's like a prime protected carry-on that schneier carries)
thank you for the education :) this is so good!
Luggage that would make Dan Brown green with envy.
Needlessly confusing if Dan Brown is green and Dan Green is white. Somebody standardize Dans.
Danny White is white, so that's a start
Nice and tentative congratulations.
I use to run Mersenne Prime Search (GIMPS), but now all I have is laptops. It runs to hot on the Laptops I have :(
Will need to play with throttling some more.
Edit: found mprime (mprime-bin-24.14) is available in NetBSD pkgsrc. But this uses 32 bit linux emulation to execute, I have been trying to avoid it, but may try it.
Finally! Just when I thought everyone had moved their spare compute to more lucrative schemes.
It’s the longest wait for a new mersenne prime since the discovery of M32 in 1992.
amazing how many bitcoins have been discovered since then. Satoshi should've incentivized mining something useful.
Are these high Mersenne primes all that useful?
I've been thinking there should actually be more useful (or at least more interesting? :P) crowd computing stuff.
How about something like Superoptimizing (with correctness proofs) open source code?
I think there's actually a fair number of them, but more would be nice. Lots of protein folding ones, and there used to be a weather/climate related couple.
every new prime for new block, but not linear.
Awesome. I have been recommending in my organization, 24 Hrs. Prime95 Stress Test as part of acceptance protocol for all new servers ! Happy to see it find another record Mersenne Prime.
y-cruncher is the king of stress testing
Given this contest can presumably go on infinitely long, what is the ultimate point of the contest? Is there some kind of theoretical or practical benefit to discovering a new Mersenne prime?
The EFF Cooperative Computing Awards, which pay out money for (four specific sizes of) prime records, were meant to show off how the Internet is useful for letting people who don't even know each other work together to solve problems. They were established back in 1998, when people in general were much less familiar with the Internet and its impact. That specific contest isn't set up to go on forever, as it ends when a billion-digit prime is discovered.
The search for different kinds of mathematical objects sometimes has applications and sometimes doesn't. For example, apparently the search for Golomb rulers (another distributed computing project) has some conceivable applications.
https://en.wikipedia.org/wiki/Golomb_ruler#Practical_applica...
There's a misconception (that I heard dozens or hundreds of times when I was running the Cooperative Computing Awards at EFF) that discovering world record primes is useful to cryptography. In fact, it has no direct application because all of the primes used in number-theoretic algorithms like RSA and classic Diffie-Hellman are dramatically smaller than world-record sizes, and can be generated on an ordinary PC in seconds. (Try "openssl prime -generate -bits 2048" at your command line!)
(There is a wild paper from 2017 called "Post-quantum RSA" arguing that we could in principle just scale up RSA keys for post-quantum security, but that paper uses multiprime RSA moduli composed of large numbers of 4096-bit primes, instead of just the traditional two primes, so even that approach doesn't require individual primes that are especially large or hard-to-find by computer standards.)
We have apparently learned a bit about number theory and algorithms as a result of research done by the GIMPS project and its collaborators about how to optimize some of the arithmetic in the GIMPS client. I guess that's the equivalent of the claim that the space program produced various spin-off technologies while pursuing space exploration.
In general, since there are infinitely many primes, there's no reason that humanity can't keep looking for larger and larger ones indefinitely. Likewise for many other searches, both for objects which are known to be infinitely numerous and objects which may or may not have a largest example. Mostly this kind of activity has a "because it's there" flavor to it.
https://en.wikipedia.org/wiki/George_Mallory
Research mathematicians are mostly not that excited about this activity, because it isn't generating more understanding or hypotheses about mathematical structure. They're usually more excited about insights that reveal or hint at new patterns or structure, which searching for large primes doesn't really do (most of the work is mechanical, performed by computers, and the outputs aren't very surprising or suggestive in a mathematical sense).
I've hoped that publicity about discoveries like record primes might get more young people interested in mathematics (and maybe about topics like number theory and discrete math that they might not be encountering in school). I got kind of a sad view of this because people were constantly writing to me asking for monetary rewards for their inevitably-mistaken-or-confused "discoveries", but I'd like to think that there are also people out there who got curious about what we do and don't know about primes. A good place to start with that is the Prime Pages
https://t5k.org/
And wasn't that paper just poking fun at people who still used something as outdated as RSA as the default public key crypto primitive in the 2010s by extrapolating their position to its logical extreme?
I think there was an intended humor element there, particularly since some of those people were also working on new post-quantum primitives, but they also "committed to the bit" and did the research for real.
To learn something about primes.
Perhaps there is a pattern or a way to more-accurately predict which numbers will be prime.
Also, it is cool.
Do we expect to learn something interesting from any given new Mersenne prime discovered? Don't we kinda have enough so that if we are going to discover something interesting by analyzing them, we can do that with the ones we already know about?
I'm not an SME but I would imagine that if there's some sort of very large scale pattern in Mersenne primes then finding that might lead to the discovery of some currently unknown emergent property. Of course this argument is likely unfalsifiable, as it can scale infinitely if there's an infinite amount of them, though we don't even know whether they are a finite set or not.
Isn't the fact that a certain number is a Mersenne prime interesting in itself? Surely it's a great addition to our knowledge of numbers?
Sure, I'm not against GIMPS or anything, I'm just a bit doubtful that finding a few more Mersenne primes could be the key to unlocking some secret pattern in the primes is all
I didn't claim there are an infinite number of Mersenne primes. I said the contest could presumably go on infinitely long. The latter doesn't require the former. It's only predicated on us lacking proofs about how many there must be.
you actually almost got me :)
I mean, that's what I took from your comment here, quoting my "presumably": https://news.ycombinator.com/item?id=41888609
It's well established that there are infinite prime numbers, for example https://www-users.york.ac.uk/~ss44/cyc/p/primeprf.htm
Should be able to trivially extend that logic to Mersenne Primes then, 'presumably'
It’s not.
The traditional proof that there are an infinite number of primes relies on unique prime factorisation- i.e for any number, n, there is a unique set of primes p1, p2, p3, … etc. where p1 * p2 * p3 * … = n
For instance 88 = 2 * 2 * 2 * 11, 42 = 2 * 3 * 7
It’s worth reading the proof if you haven’t - it’s comprehensible with high school maths.
No such property exists for Mersenne primes, so we can’t trivially extend it. Many proofs of the properties of prime numbers are difficult because they, by definition, actively resist patterns.
It’s exploration of new lands
lol, like the government doesn't have 3 more Mersennes they keep secret so they can verify potential First Contact situations
the idea of a deep-nation-state-cold-war psyop campaign bluffing and escalating math proofs is so goddamn hilarious, apt, and ironic it would be almost better than the mistake of pissing off the Aliens by offending them with math homework.
"Shizuo Kakutani joked that the problem [Collatz conjecture] was a Cold War invention of the Russians meant to slow the progress of mathematics in the West."
They're much easier to verify than to find. Just ask for the next one hundred unknown primes and check the response.
This still suffers from the MitM / Two Generals Problem, and is existentially problematic if they also demand the simple, reasonable sum of the first BB(17) numbers modulo Grahams number, within 14 business local parsec-years.
Their spam filter may be an annoying ping acknowledgement, a directed gamma ray beam from soft gamma repeater, just to irradiate their own hoax-doers suspects.
If anyone is interested in knowing more, Veritasium has a good video on this, "The Oldest Unsolved Problem in Math": https://youtu.be/Zrv1EDIqHkY
Why don't they say what it is?
Because the EFF Cooperative Computing Awards for the first discovery of large enough prime numbers are still active. Publishing the probable prime in advance would risk someone verifying faster than GIMPS.
I used to run the Cooperative Computing Awards, and I don't think this is the reason in this case.
The most recent award was given out in 2009 for a prime over 10,000,000 digits in length. The next available award is for a prime over 100,000,000 digits in length.
But the most recent discovery by GIMPS prior to the current discovery was a prime with length only 24,862,048.
https://en.wikipedia.org/wiki/List_of_Mersenne_primes_and_pe...
The primes they've found have been getting longer by only single millions of digits every several years, so it's not very plausible that this discovery would qualify for a monetary award.
I suspect they just don't want to announce a number before it's verified on general scientific-integrity grounds.
GIMPS currently searches for exponents up to 999,999,999, corresponding to 301,029,996 decimal digits. We don't really know much about the exact distribution of Mersenne primes so it is possible that a new discovery was from much higher ranges and thus eligible for prizes.
But yeah, they'd probably embargoed even without any potential monetary prizes because it's wise to do so in general ;-)
Sure, but all actual historical discoveries of Mersenne primes since the 1980s have been in strictly increasing size order, with no missed primes in between found in retrospect, and the successful exponents have increased gradually rather than sharply in size. It would really buck the trend to an extreme degree if the new successful exponent were 5× as large rather than something like 1.05× as large as the previous record.
I want to make an analogy to sports records, but the analogy will obviously be imperfect because the limits of human physiology are better understood in some ways than the behavior of Mersenne primes and perfect numbers. But it might be like if we heard that the marathon record had been beaten and then it turned out that the new record was something like 1:30:00 instead of something like 2:00:00. Obviously the exact value of the new record is totally unpredictable, but the best bet is that something like long-term trend lines will continue to be followed, rather than abruptly radically changed by multiple orders of magnitude.
M43112609 (2008-08) was discovered prior to M42643801 (2009-06), so that order is not really strict. I agree that there is a human tendency to test smaller primes (thus faster to verify) first, but it should be also noted that every single Mersenne number smaller than M124399361 has been already tested at least once by someone even though that limit would be way higher than what we have for primes. There are also some groups of people that specifically look for prime numbers that are barely enough to be 100,000,000+ decimal digits [1]. Given we didn't see any new Mersenne prime for many years, new prime from a random range seems much more likely than ever.
[1] See https://www.mersenne.org/primenet/ and scroll down to the starting exponent of 332,000,000. There would be an unusually large number of assigned LL/PRP tasks around this range. In fact, this holds for virtually all available PrimeNet statuses in the Wayback machine!
Sports analogies are good, but:
Any% (Anything goes to get to the "end") Video game speedruns may be ideal - a shortcut can always be found, used by everyone to quickly become zero sum + 1, then the equilibrium re-approaches optimization; but on average, gets harder and harder, as the shortcuts take skill/power/time. It also is hard to do, and easy(ish) to verify.
For linear things that hardly have any variance, you can look at longest lifespans of humans. Notably; where living 18 months longer than the next person statistically makes it more likely that you are actually your own mother and lied.
How do you prove that you verified that a number is a prime?
If you want to prove that a number is not a prime you can show the factorization or that it breack the little theorem of Fermat with 367984321568, and everyone can check the refutation inmediately.
I don't know a similar method to show that you actualy verified the number is a prime.
There are primality proving certificates.
https://en.wikipedia.org/wiki/Primality_certificate
These are sometimes infeasible for stupidly big numbers, but the Mersenne Primes have a specific structure that allows for simplification of the process.
It's hard to see how that someone would count as the discoverer.
That someone will totally count as the discoverer under the current rules [1], because it requires the deterministic primality proof for given number. It doesn't matter how much effort was taken to reach that candidate so far, even though it would be virtually impossible to find any new prime without that. I think the temporary embargo is fully justified for this reason.
(And I think it is technically possible to probe the reports to find what it was anyway, but it is not easy to find one at least for me. If you are really looking for that, look for the P-PRP result type.)
[1] https://www.eff.org/awards/coop/rules
Is there a probabilistic test for Mersene primes? I thought they just wanted confirmation via independent calculation.
Any probabilistic primality test will work, but GIMPS currently uses the first-time Fermat probable prime test with a very robust certificate [1] to filter almost all non-primes in advance.
[1] https://www.mersenne.org/various/math.php#prp
How hard?
NP hard?
I wonder why?
:)
Or even the number of digits.
Are there statistics on the scale of compute available to GIMPS for this search? Is there any evidence that by crowdsourcing the clients, we are searching faster than, eg, a dedicated cluster financed by a government or a corporation? What is the impact of GIMPS as a distributed problem solving tool? Like, if there was a practical application, how much money would it take to exceed GIMPS throughput, that curious people provide for free?
I’d like it to be astronomical, but given the niche of this, and the low cost of cloud compute, the answer is predicable depressing, like, “$50k/year in AWS costs would equal current GIMPS search throughput”
https://www.mersenne.org/primenet/ suggests 127 PFlop/s average over the last month, which would put it in the top 10 on https://top500.org/lists/top500/2024/06/
I used a random estimate online for computing cost which had 5.6e17 Flops per dollar on A100s gives about a dollar every 4.4 seconds or ~$7 million per year.
Sadly, I do not vouch for the correctness of any part of this, though I did try.
> “$50k/year in AWS costs would equal current GIMPS search throughput”
I think you may be wrong by at least 3 orders of magnitude.
For others that, like me, do not know… a Mersenne prime is when the n is prime and the resulting M is also prime in the following equation.
M = 2ⁿ - 1
I didn’t know, but according to Wikipedia we don’t need to require `n` to be prime, because when it isn’t, then neither is 2ⁿ-1. https://en.wikipedia.org/wiki/Mersenne_prime
So I prefer to shorten the definition to "A prime of the form 2ⁿ-1". It’s bloody useful that n has to be prime though: makes searching that much faster.
But why do we have to "discover" it when we know the formula would be 2^N - 1...? Are we trying to prove a corollary or what?
There’s tons of numbers of the form 2^N-1 which are not prime.
To discover the primes, we have to iterate through the numbers and test their primality. With numbers that are so big, it’s very compute intensive
Not all 2^N - 1 are prime. For example, N=18 makes 2^N - 1 = 262143, which can also be written as 3^3 * 7 * 19 * 73 (not prime).
Oh, right, all Mersenne number is in the form of 2^N -1, but Mersenne prime is Mersenne number plus being prime
And we look for Mersenne primes, AFAIU, mainly because Mersenne numbers are more likely to be prime than other numbers, so it's easier to find big primes that way.
A lot simpler example is 2^4-1=5*3
2^11-1 (prime power) for a less trivial example
https://oeis.org/A000043
I always wondered if we could parallelize a prime test on GPU. That would give us a Datacenter level compute and really help us scale, but it might be too hard to do.
https://github.com/preda/gpuowl
I turned 40 recently and it was the only devastating milestone before or since. No excuses: I blew that.
Still no Prime95 release build for Apple silicon
Hell yeah!! This is the best thing to happen all week!!!
Great news for humanity.
We get free two-day shipping on our Mersennes.
Thanks, Jeff!
Chuck Norris has already discovered and factorized all the prime numbers.
A number is prime if its factors are itself, one, and Chuck Norris.
A number is prime if it is the number of times Chuck Norris roundhouse kicked Optimus Prime