4 ms·
"Finding random big primes p and q is easy" For those wondering why then, it is news when a new largest prime is found: there are gradations of 'big'. The big
by Someone 13y ago
"Finding random big primes p and q is easy"
For those wondering why then, it is news when a new largest prime is found: there are gradations of 'big'. The big primes used in cryptography have fewer than 1000 bits, or about 300 digits. That is not what one (nowadays) calls 'large' in the field of finding the largest prime. There, one laughs at numbers of a million digits (the largest known prime has 17,425,170 digits)
- csense 13y agoAlso, for a practical engineering problem, like writing an RSA implementation which will be used in an SSL implementation which will encrypt credit card numbers on an e-commerce website, it is okay to use probabilistic tests which have a tiny chance of a false positive (the test claims a number is prime when it is actually composite). You can generally repeat a probabilistic test with different parameters to make the probability of a "false positive" prime number very tiny -- like .000 000 000 001 -- while still staying within the computational budget manageable on an ordinary computer (obviously, a practical Internet security scheme should be able to complete its computations in a second or two on a typical desktop, laptop, server, and smartphone). So probabilistic tests are good enough for practical purposes, but you need a non-probabilistic test to get the false positive probability all the way down to zero. And you need to use a method that has zero percent false positive chance to claim a world record. The EFF-administered monetary prize for a record-breaking prime number, for example, requires "the primality proof must be a deterministic proof..." [1] So you can't use probabilistic methods. [1] https://www.eff.org/awards/coop/rules https://www.eff.org/awards/coop/rules
- mistercow 13y agoI know (or think) that most record primes these days are Mersenne primes due to the relative ease of testing their primality. What I wonder is if probablistic tests could be used to find candidates for very large non-Mersenne primes before testing them using AKS. Or is o̅(log⁷·⁵(n)) just infeasible for those sizes of numbers?