[test77777]

If you just make up a number claim it’s prime and nobody disputes it, it’s prime apparently. I don’t think it’s really possible to have a very large prime number, because unless someone has tried every factor it’s really not prime yet, honestly that explains a lot about the elusiveness of the concept.

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

[vlovich123]

The primes used in RSA are definitely randomly generated for each new key, unless I’m misunderstanding what you’re trying to say. And afaik determining that the random number is prime is a mixture of “generate a random number using a formula that has a high probability of generating primes” and various probabilistic primality tests. It’s possible AKS has been incorporated to prove the numbers are prime in modern implementations, not sure. But historically RSA traditionally (definitely before 2006) determined primality probabilistically.

ECC doesn’t require primes and so is safer in that respect although I’ve been hearing that ECC might have structural deficiencies that causes a swing back to RSA for the most secure applications.

[adgjlsfhk1]

deterministic tests generally aren't used because the brobibalistic ones can easily get you to a guaranteed chance of 2^-100 of not having a false positive which is enough that it is dramatically more likely that 6 cosmic rays came and flipped the answer than a false positive.

[vlovich123]

Yeah I didn’t think anyone used deterministic ones because speed, but I don’t know how much faster probabilistic variants are because if the deterministic ones aren’t too much slower I could imagine the added safety margin would be more useful assuming that key generation isn’t a critical path in an application (which it shouldn’t be because typically you don’t generate many many RSA keys dynamically)

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

[test77777]

Ok then break all cryptography with that. It just proves my point you can SAY you can do it but in practice you can’t.

[ndsipa_pomu]

Cryptography is about finding large prime factors of a large number. That's a much harder problem than just determining whether a specific number is prime or not.

[test77777]

I don’t understand you just say it was about finding factors, okay yeah that determines whether a number is prime. You’re not telling me anything I don’t know, I just disagree with your stance.

[eigenket]

AKS is an example of a deterministic algorithm which works out whether a number is prime or composite and runs in polynomial time in the number of bits in the number.

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

I'm not sure why you would expect this to break all (or any) cryptographic protocols.

[adgjlsfhk1]

prime testing is much easier than factoring. you need to factor to break rsa

[Ar-Curunir]

Some cryptography depends on hardness of factoring, not hardness of checking primality.

[bigbillheck]

How would that work?

[sweezyjeezy]

The article starts by saying mathematicians want things to work for large numbers, but that doesn't really get to the crux of the issue with primes. Infinite sequences are ubiquitous in number theory, and in general it will be infeasible to have a test for inclusion in these sequences for large enough numbers. But often they have structure that we can use to characterise them very precisely - think about square numbers, it's easy to say what the trillionth square number is, what it's remainder when you divide by 13, etc.

What makes primes hard, and also interesting, is that they seem to be extremely unstructured, we believe they behave like a kind of random number generator, even though they are clearly not random. In fact many of the theorems and conjectures mentioned in the article actually hinge on this. Random numbers are unpredictable on a small scale, but on a large scale they have very nice distributional properties, whereas more structured ones of similar growth rate will often have undesirable restrictions on them.

[credit_guy]

You should check the concept of "primality certificate".

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