Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

GIMPS Project Discovers Largest Known Prime Number

mersenne.org

Post reply on HN
Print view View original

71–80 of 115 posts

Re: GIMPS Project Discovers Largest Known Prime Number

#71

Post by sowbug »

schoen wrote: post #25
kryptiskt wrote: post #18

Earlier quoted context omitted.

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.)

Re: GIMPS Project Discovers Largest Known Prime Number

#72

Post by chimeracoder »

netcraft wrote: post #15

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 hardd…

> 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.

Re: GIMPS Project Discovers Largest Known Prime Number

#73

Post by emmelaich »

netcraft wrote: post #15

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 hardd…

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

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

Re: GIMPS Project Discovers Largest Known Prime Number

#75

Post by kristianp »

thomasahle wrote: post #67
biot wrote: post #12

Earlier quoted context omitted.

> 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”.

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.

Re: GIMPS Project Discovers Largest Known Prime Number

#76

Post by grzm »

sillysaurus3 wrote: post #58
lettergram wrote: post #50

Earlier quoted context omitted.

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.

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…

Have you considered https://lobste.rs ?

Re: GIMPS Project Discovers Largest Known Prime Number

#77

Post by jacobolus »

Cyph0n wrote: post #59
schoen wrote: post #29

Earlier quoted context omitted.

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é, ....

Re: GIMPS Project Discovers Largest Known Prime Number

#78

Post by Someone »

netcraft wrote: post #15

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 hardd…

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.

Re: GIMPS Project Discovers Largest Known Prime Number

#79

Post by Someone »

sowbug wrote: post #71
schoen wrote: post #25

Earlier quoted context omitted.

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 i…

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.

Re: GIMPS Project Discovers Largest Known Prime Number

#80

Post by yjftsjthsd-h »

WhitneyLand wrote: post #49

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

"Because it's there."

- George Mallory

Post reply on HN