3 ms·
What you need for cryptography is to be able to reliably generate hard instances. It's actually easy to factor most numbers--½ of all numbers are divisible by 2
by jcranmer 9y ago
What you need for cryptography is to be able to reliably generate hard instances. It's actually easy to factor most numbers--½ of all numbers are divisible by 2, and ⅓ of all numbers are divisible by 3. What's difficult is factoring products of similar-sized primes, and generating arbitrarily large primes is fairly easy. When you look at, say, graph coloring or graph isomorphism, it turns out that most named classes of such graphs turn out to be fairly easily solved, which means generating the instances that can't be solved easily is difficult.