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

[adgjlsfhk1]

A lot of the problem is that the types of people who care about deterministic results care more about asymptotic runtime than wall clock runtime. The other problem is that the asymptotics of AKS are still pretty bad (log(n)^7.5 vs log(n)^2 for Miller Rabin).

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

[ndsipa_pomu]

I don't understand your stance.

You seem to be claiming that the ability to determine whether a number is prime or not is extremely difficult and that it would break (some) cryptography if it were no so. My stance is that (some) cryptography would not be broken unless factorisation of large numbers into two large primes becomes easy.

Can you clarify how you think that some cryptography is broken by a relatively simple test of whether a large number is prime or not?

[adgjlsfhk1]

primality checking is much easier that factoring. it's somewhat unintuitive, but there are deterministic methods of primality testing that don't tell you the factors.

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