A new generation of mathematicians pushes prime number barriers

Post by adgjlsfhk1 » Mon, Oct 30, 2023, 5:34 AM UTC

vlovich123 wrote: post #21

magneticnorth wrote: post #18

Earlier quoted context omitted.

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.

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 impl…

Post by adgjlsfhk1 » Mon, Oct 30, 2023, 3:30 PM UTC

vlovich123 wrote: post #32

adgjlsfhk1 wrote: post #31

Earlier quoted context omitted.

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.

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)