[netcraft]

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.

[OscarCunningham]

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.

[soVeryTired]

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

[chimeracoder]

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

[qmalzp]

Nit: the largest prime discovered is

2^(277,232,917)-1

not

2^(277,232,917-1)

[Franciscouzo]

If you read the article, it's actually:

(2^77,232,917)-1

[chrismorgan]

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

[TheRealPomax]

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.

[kodablah]

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

[seppel]

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

[Someone]

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.

[raverbashing]

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

[zeep]

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

[schoen]

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.

[ehsankia]

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.

[mygo]

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.

[TheRealPomax]

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.

[kryptiskt]

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.

[schoen]

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.

[sowbug]

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

[Someone]

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.

[schoen]

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

[OscarCunningham]

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.

[xamuel]

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"

[schoen]

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

[fooker]

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

[schoen]

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.

[JackFr]

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

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

[deckar01]

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

[adrianN]

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.

[bmm6o]

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.

[emmelaich]

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

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