4 ms·

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

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 3y ago
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 3y ago
  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 3y ago
    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 3y ago
      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).

vlovich123 3y ago

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 3y ago
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 3y ago
  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 3y ago
    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).