[akarve]

> If you just make up a number claim it’s prime and nobody disputes it

You can test if a number is prime in polynomial time, much faster than a sieve. There’s no need to test every divisor to know whether a number is prime or not.

Algos like RSA generate large primes millions of times every day—-there’s nothing to take on faith.

[creata]

Doesn't RSA typically settle for numbers that are probably prime?

[akarve]

Technically I think so, so there’s a tiny bit of faith for RSA but absolutely none for primality in general https://en.wikipedia.org/wiki/AKS_primality_test

[test77777]

I’d argue that you’re just misunderstanding what makes a number prime. You can literally never be 100% sure a randomly generated number is or isn’t prime, it’s just the way numbers work.

[magneticnorth]

I think you have some confusion about RSA cryptography - it relies on numbers that are deliberately generated using very large (known) primes, so these numbers are definitely not "randomly generated".

It takes a short time to generate such a number but a very long time to decompose it, but this is a different problem than telling whether a number is prime.

[JonChesterfield]

Counterexample, roll a dice. That gives you a randomly generated number. You can then test whether said random number is prime by enumeration.

[Ar-Curunir]

There is literally an entirely deterministic algorithm for checking primality, so you can be 100% sure that a randomly-generated number is prime: https://en.wikipedia.org/wiki/AKS_primality_test

[adgjlsfhk1]

you absolutely can. aks is a polynomial time deterministic primality check.