4 ms·
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 whic
by 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 agoYeah 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 agoA 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).