Hacker News new | comments | show | ask | jobs | submit login
GIMPS Project Discovers Largest Known Prime Number (mersenne.org)
369 points by seycombi 9 months ago | hide | past | web | favorite | 108 comments



So that's what it's working on when it's starting up.


GIMPS = Great Internet Mersenne Prime Search. Completely unrelated (apart from similar naming) to the GIMP (GNU Image Editing Program).

Perhaps you were joking; but I'm sure others might be confused.


That was very clearly a joke. Good one too.


I know typically jokes like this aren't HN material, but have an up vote lol

Literally, the first thing I though of was GIMP as well :)


It seems to me that jokes are ok, just not spamming the same old jokes, as you might on Reddit.


Mm, if something is subtly funny, it's usually welcome.

One of my favorite jokes of all time was pg's nickb april fools prank: https://news.ycombinator.com/item?id=151109#152361

Probably worth putting together a list of HN moments... There were so many.


Reading over that, I actually recognize I miss the older HN - where the conversations seemed fairly long and in depth. It's still often the case, but it does seem like the average length and depth is decreasing.


"Nostalgia was better in the old days" ~ unknown author


"I remember when I used to be really into nostalgia"

- Demetri Martin


I completely agree. There are a few contributing factors, none of which are unsolvable. But it seems like the way to solve it is to essentially fork HN.

The current plan is to create a "mirror" of HN's front page, but with a smaller community. You'll be bale to keep your HN name, because you won't be allowed to use someone's existing HN name on the new site unless you claim it.

Then, we'll need content. This was the secret sauce in the early HN days. The sole reason for people to come to the new site would be good conversation, and I think recruiting a few of the writers from HN would be enough to bootstrap it. Part of HN's early success was that pg actually participated in HN. Whereas the current mod team just shows up to beat us over the head and little else.

If you want to help plan this out, contact me (email's in profile). I think we have a shot at this. Some past thoughts on the topic:

https://news.ycombinator.com/item?id=16064078

https://news.ycombinator.com/item?id=16044466

Getting away from the heavy-handed moderation will be the best part. Comments will be free to flow into tangents, as long as they're substantive.


What did the mod team do to you? This is the second time I've seen you have a go at them today.


Have you considered https://lobste.rs ?


Agreed it's too good


Mm I didnt get the joke about pg, care to explain?


"Loading data files" is code for "secretly computing prime numbers"


GIMP startup is only a few seconds if you have a decent SSD. I certainly remember it taking a long time on mechanical drives.


GIMPS[tartup]


Can anyone explain why it takes so long? It also seems to launch a lot faster on linux than on macOS, I wonder why.


I also was thinking of GNU Image Manipulation Project


> Jonathan Pace is a 51-year old Electrical Engineer living in Germantown, Tennessee. Perseverance has finally paid off for Jon - he has been hunting for big primes with GIMPS for over 14 years.

What a great story.


I know he's a volunteer but only $3000? Does that seem low to anyone else?


For producing something of no intrinsic monetary value?


How are these any different from say Bitcoin?


Bitcoin doesn't pay out cash when you find a block. It pays out Bitcoins. So the value of that is based on how much other people will pay for a bitcoin.


people pay for Bitcoin


You can buy things with Bitcoin.


You can buy things with $3000 cash as well.


But not a Bitcoin


I don't think anyone is doing this to make a quick buck, just for fun.


He's probably spent more than that on electricity to max out his CPUs for 14 years.


so I didn't know this, but got curious about how many known prime there are - I knew there were infinite primes, but thought that there would be some concrete list of all the primes that we had discovered somewhere - but apparently not

https://math.stackexchange.com/questions/272791/how-many-pri...

> Nobody's really keeping count. ... There are very many hundred-digit primes to find. We could cover the Earth in harddisks full of distinct hundred-digit primes to a height of hundreds of meters, without even making a dent in the supply of hundred-digit primes.


I also used to think that there weren't very many primes. But the prime number theorem says that the number of primes less than n is about n/log(n). The function log doesn't grow very fast, so a large proportion of numbers are prime. For example the number of primes less than 10^100 is 4*10^97.

Primes are really really common.


Much more common than square numbers, for example. sum(1/n^2) converges, but sum(1/p) for p prime doesn't.


> so I didn't know this, but got curious about how many known prime there are

This isn't the exact question you're asking, but we actually know the distribution of prime numbers, which allows us to calculate the (approximate) number of primes that are less than or equal to an arbitrary value.

Since the largest prime discovered is 2^(277,232,917-1), that means that the number of primes less than or equal to that number is approximately equal to 2^(277,232,917-1)/ln(2^(277,232,917-1)).

That's approximately equal to:

2^(277,232,917-1)/ln(2^(277,232,917)), which is in turn equal to 2^(277,232,917-1)/(277,232,917 * ln(2)).

That's a number that's too big to plug into your standard everyday calculator, but that tells you the number of primes you could "discover" and still not break the (new) record.


Nit: the largest prime discovered is

2^(277,232,917)-1

not

2^(277,232,917-1)


If you read the article, it's actually:

(2^77,232,917)-1


Very well then; let us rather write them with proper superscripts (and I’ll use THIN SPACE as a thousands and prettiness separator too because I can):

2 ⁷⁷ ²³² ⁹¹⁷ − 1

not

2 ⁷⁷ ²³² ⁹¹⁷ ⁻ ¹

There, no more ambiguity.

(Now I’m waiting for someone to jump on me to correct anything subtle.)

[Ah, I see, the parentheses were indeed a red herring. Ah well; let the superscripts remain.]


Not sure if this was a serious comment, but if it was: due to operator precedence in mathematics, the expressions (2^77,232,917)-1, 2^(77,232,917)-1, and 2^77,232,917-1 are identically evaluated, with the parentheses only used to aid the human eye. This in contrast to 2^(77,232,917-1), which is 2^77,232,916 and is a very different number indeed.


The parens are a red herring. GP is commenting on the previous poster using 277 instead of 77 (i.e. typo).


> but thought that there would be some concrete list of all the primes that we had discovered

It is trivial (in computational power) to find a random prime in order of 2^2048. So such a list would be way to big to store somewhere and always be out of date. It is not hard to find very big primes. It is just hard to find very very big primes.


RSA encryption (https://en.wikipedia.org/wiki/RSA_(cryptosystem), used in PGP, TLS certificates, among others) is based on the fact that I know a pair of primes you don’t know, so even if somebody tried to keep such a list, it better be incomplete.


The relevant thing is not that's a prime (it's pretty trivial to find one), but a Mersenne Prime

Primality testing is not trivial at those number sizes


not really, it is very hard to test any very large number for primality... this project only test numbers that satisfy the Mersenne prime definition though... 9 of the 10 known largest primes are Mersenne prime numbers probably because there is more people testing these numbers.

http://primes.utm.edu/largest.html#biggest


But the biggest reason that the largest known primes have this form is that they are subject to a much faster special-form primality test.

https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality...

There's no known general-form primality test that is nearly as fast for numbers of corresponding sizes.


People test these because it's the easiest pattern we know of for constructing large primes. So if you want to maximize your chances of finding a large prime, you'll check for the mersenne form.


people test these because we have the technology to check if a large number of the Mersenne form is prime at a faster speed than numbers that do not conform.


That list would be as long as the list of "all even numbers" because any list of primes immediately gives you a next prime that should be on the list, but isn't, in the same way that having a list of even numbers immediately gives you the next even number that should be on that list but isn't:

Given an ordered list of primes {2,3,5,...,n} one (of several) immediately known next prime number is simply (2 x 3 x 5 x ... x n) + 1. We know that number's prime because it cannot be cleanly divided by 2, or 3, or 5, or ..., or n.

As such, even if it might be useful to have a list of all known primes, annotated with what kind of prime each number is, such a list cannot be constructed: even just the subset of all prime numbers generated based on the simple above rule would be infinitely long, just like the list of all even numbers is infinitely long.


RSA encryption keys uses the product of two large primes, where each prime is many digits long. So many new primes are "discovered" every day.


Interestingly, those primes' primality is normally proven statistically rather than deductively. This is not really a practical issue for people using RSA, but could be a philosophical issue for someone interested in the question of how many different numbers' primality has been proven by humanity.


Not that I worry about this much, but if the fast prime generation methods we use are imperfect, then how bad is it when someone's PGP key or TLS certificate is based on nonprimes? Do black-hats ever strike gold and find out that someone's key is easily factorable? Or is there an additional property of common primality tests that their errors tend to be insignificant? (e.g., yes, this number isn't really prime, but its factors are very likely to be so large that they are also impractical to find, rather than, say, divisible by 7.)


Yes, but not because of the use of non-primes, AFAIK. There also are ‘bad choices’ for the primes that one should avoid.

See https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Faulty_key_..., https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Importance_...

Also, for those that are concerned about doing statistical primality tests, there are fast deterministic tests (https://en.wikipedia.org/wiki/Primality_test#Fast_determinis...). Read https://en.wikipedia.org/wiki/AKS_primality_test for pointers to the algorithms to use in practice.


I think there was some research about this that did find some flawed implementations leading to semiprime p or q, but basically you can choose the probability that a probable prime is actually composite to be low enough that the expected number of weak keys ever generated for this reason is still less than one.

(I haven't personally understood the probabilistic primality tests well enough to understand how they guarantee that the probability of error contributed by each round of the test is completely independent of every other round.)


In fact if someone worked out how to crack RSA when it turned out that one of those numbers weren't prime then they would have invented a fast primality check. Which would be really cool in itself, and allow RSA to be fixed.


When philosophers study mankind's knowledge, it's more typical to study the things mankind would ideally know at the end of all time assuming mankind could continue forever.

(Formally: the knowledge predicate is usually assumed to satisfy modus ponens: if mankind knows "A implies B" and mankind knows "A", then mankind knows "B")

Under this abstraction, if mankind knows the axioms of logic and Peano arithmetic, then mankind [ideally eventually] knows the primality of all primes.

Contrast: Which Turing machines will mankind [ideally eventually] know are never-halting? This is a much harder question and the answer is probably not "all never-halting Turing machines"


It's a little funny that mankind gets to use a full-fledged infinite-tape Turing machine in order to compute arbitrarily large computations, since no such machine would fit in our universe.

https://en.wikipedia.org/wiki/Limits_of_computation

https://en.wikipedia.org/wiki/Transcomputational_problem


The description of a Turing machine that can do arbitrarily large computations can be finite. See: Kolmogorov complexity.


Sure, but it feels a little funny in one way to say that people "know" all of its output, although I'd agree that for other purposes being able to write a program to generate something is a relatively good description of what it means to understand it.


> then mankind [ideally eventually] knows the primality of all primes

We already know the primality of all primes. They're prime. All numbers though . . .


RSA implementations do use probabilistic primality tests when generating primes. OpenSSL [0] uses the Miller-Rabin primality test for RSA, which can be wrong, but they use enough iterations to make it very unlikely.

[0]: https://wiki.openssl.org/index.php/Manual:BN_generate_prime(...


I don't know to what confidence ssh-keygen and the like test their candidates, but it's not hard to make the probability for composite smaller than the probability that the computer doing a proper primality test is hit by an asteroid while doing the computation.


Not only are there an infinite number of primes, there are so many that the inverse series diverges. That is, Sum 1/p_i is infinite.


Reading the GIMPS forums, some think they've missed a few.

The occurrence rate is surprisingly (or not?) irregular.


tl;dr The 50th Mersenne prime was just found by a volunteer of the GIMPS (Great Internet Mersenne Prime Search) project. It is 2^77,232,917-1 and has 23,249,425 digits. Mersenne primes are extremely rare and are always of the form 2^p-1 for some positive integer p. The first four Mersenne primes are 3, 7, 31, and 127.


Also, p is prime.


Just to clarify, in this case p = 77,232,917 is prime, but for Mersenne primes in general p is just a positive integer.


Not quite. If p isn't prime then 2^p - 1 isn't prime.


But why?

One answer is a bit buried in a sub link in the article. On that page, you’ll find arguments for the following reasons: tradition, by products of the quest, collection of rare mathematical things, glory, pushing hardware performance, and contest rewards.

Personally I’m forced to admit I enjoy seeing them found while being unable to form any cogent justification.

http://primes.utm.edu/notes/faq/why.html


That's actually a fairly complete and accurate list of reasons for such a project. If I was interested, I'd do it for about half of those reasons, and others may prefer the other half.


They're a nice source of mathematically justifiable entropy.


"Because it's there."

- George Mallory


Prime numbers are amazing.

I was watching a math documentary and one example was a Cicada in North Carolina that only emerges once every thirteen years millions of them at once. It's a defense mechanism the sheer number overwhelms predators. The Cicada does this also to avoid appearing when another species of Cicada appears to prevent cross breeding.

The other species in the same region emerges every 7 years. The two will only emerge at the same time every 220 years (I think it as).

Smart bugs!


I vaguely remember watching the same documentary, so I don't doubt you. But surely they would emerge at the same time every 21 years?

Edit: I looked it up, its 13 and 17 years, giving a 221 year overall cycle. I guess it only really "matters" that the years are coprime.

https://en.wikipedia.org/wiki/Periodical_cicadas


This is a similar concept to the odd numbers of teeth used in gear chains. If you had an 8-tooth and a 16-tooth gear, they will wear unevenly as the same teeth (with potential manufacturing defects) always meet the same teeth. If you change that to 7-tooth and 17-tooth, they will only repeat pairings every 119 teeth and wear will be distributed evenly across all teeth. In general, tooth numbers that are relatively prime (sharing no divisors) are preferred.


Is this the 3-part BBC documentary - "The Code"?


Yes I think that's what it is.


Is there a web service where you can buy a large number with certain length? Not a Mersenne prime, but just a number and/or a prime?

It needs to comply with the 2^n-1 formula. Let's say I want a number long 100 000 000 or even 1 000 000 000 long. Or a prime above that length.

Do you know how much would that cost per number prime and non-prime?


January looks to be a good month for discovering large prime numbers! As a former contributor to the project it would be great to have a primer on the best way to contribute today, covering the options for CPUs vs GPUs and the various projects for factorizations vs primality tests.


TIL I work at the same company as the discoverer of the 50th known Mersenne Prime.

I know at least one sysadmin who used GIMPS as a burn-in program for new servers.....


It’s common for stress-testing overclocking, too: https://en.wikipedia.org/wiki/Prime95#Use_for_stress_testing


I use Prime95 to test for usage-related recording lags for sound and video recording in our lab equipment. If we're not getting signal de-synchronization with that slamming the CPU(s), we can worry a bit less.


As someone who knows nothing about advanced mathematics, could someone explain why this matters? (i.e. beyond that this is rare and theoretically interesting)


It doesn't, really. It's just a novel prime that happens to be a Mersenne number (2^n - 1).


The link has another link to a page describing why this matters:

http://primes.utm.edu/notes/faq/why.html


  > Mersennes are beautiful and have some surprising applications.
Unfortunately that page doesn’t elaborate on what these surprising applications are, which is itself surprising on a page that purports to answer “why”.


It automatically results in the discovery of a new perfect number. :-)

https://en.wikipedia.org/wiki/Euclid%E2%80%93Euler_theorem

(combining two of history's greatest mathematicians with names that have confused generations of students by being pronounced very differently)


Euler and Gauss are (for now, at least) in my opinion the greatest mathematicians of the past two millenia (1000-1999, 2000-). Al-Khawarizmi takes the cake for the millennium before that. Then it's Euclid all the way back ;)


We know almost nothing about Euclid: we can figure out when he was active to within a century or two, and according to Pappus writing 500 years later some of his students/followers lived in Alexandria where Apollonius studied with them. That’s pretty much it for biographical details.

The earliest remaining editions of the Elements have no author mentioned, and our source that Euclid compiled it is a brief remark from Proclus 700 years later. Most of what is in the Elements was results from earlier, and it’s all but impossible to break down which bits were first done when or by whom. Most of what we can see today of the Elements or Euclid’s other books is later copies, much of it probably added/changed/reordered/... later.

If you want a 2000-year-old idol, go for Archimedes.

In the last 1000 years, the most influential mathematician is surely Newton, with an honorable mention for Leibniz. For the computer age (from 1950 through the upcoming few centuries), I’d put my vote on Grassmann (1809–1877), though his work was long ahead of its time and still substantially underappreciated.

Euler and Gauss were of course both brilliant and prolific and well worth studying, along with Descartes, Lagrange, Riemann, Poincaré, ....


One application is that it's fairly cheap to take `n mod p` when `p` is on the form $2^q-1$. In particular

   x ≡ x mod 2^q + ⌊x/2^q⌋ (mod p).
If you are making a hash function, and need to take mod a prime, this is useful.

Another application of slightly larger Mersennes is https://en.wikipedia.org/wiki/Mersenne_Twister


I imagine these record-breaking primes are too large to be useful in a hash function though.


Certainly. These are just for fun, or maybe in the future giving some motivation for some number theory conjectures. Who knows.


Those reasons boil down to people liking novelty. Finding new primes is just one particularly nerdy form of that.


These numbers are for as far as we know irrelevant for mathematics.


Curious: can bitcoin mining rigs be modified for BOINC projects (GIMPS, Seti@Home, etc.)? If yes, than I might invest in some rigs and modify them to run BOINC.

Yes, I'm weird: I prefer to do computation for BOINC than for bitcoin. :-)


nowadays bitcoin mining rigs use ASICs that are optimized for the task, so I don't think that would be a good idea.

on a general purpose system you can use GPUs and BOINC with SETI, not sure about GIMPS.


I see. Thanks.

I do have some PC systems but they are shared among family members, making it difficult to run BOINC as a background task without interfering with their work.

I'll look at low-cost systems, like the Raspberry Pi, to see if I can use them as dedicated BOINC boxes instead.


Indeed, Bitcoin ASICs are not only "optimized" for the Bitcoin mining task (computing a particular hash function), they usually literally don't include the logic to perform other general-purpose computations at all! That's a big contrast with GPUs.

There have been interesting discussions about a cryptocurrency whose proof of work task would be something in some way more interesting or more useful than partial hash collisions, but I don't think many such systems have caught on. There is a prime-related one called Primecoin:

https://en.wikipedia.org/wiki/Primecoin

So, I guess that's a precedent for creating new cryptocurrency designs that do something else. I don't know if there's a way to make any of the BOINC tasks into cheap-to-verify PoW systems or if anyone's tried to do so, but that might be a cool project.


Is there actually any use to discovering ever-larger prime numbers?


I know that's probably not what you mean but there is money prizes: https://www.eff.org/awards/coop


Because they're there...


Cryptography


There's no cryptographic use in finding a largest prime. It's far larger than any prime used in a practical system and doesn't contribute any mathematical knowledge about primes.

It's mostly just running an algorithm for long enough to pay off.


Come on, stop spreading nonsense. These huge primes are irrelevant for cryptography.


I believe the classic joke goes,

"Now Bruce Schneier needs to change the code on his luggage"


If you hack his computer, you can find the next largest known prime?


lol


I know that humans want to know these things, but can someone ELI5 why this important?


Consider it something like a benchmark of human progress.


There is rarely a submission here on Hacker News that has comments of such bad quality as this submission has.

I see a similar phenomenon with press. They "hype" something they barely understand, change parts of the story to make it more interesting, or invent new words (Cyber!). This is a disservice.

What do you do to avoid this noise?




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: