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