Comment by ndsipa_pomu

Cryptography is about finding large prime factors of a large number. That's a much harder problem than just determining whether a specific number is prime or not.