Some of our current cryptography schemes are based on it taking time to factor large numbers, but this is not the same thing as finding prime numbers. The basi

Some of our current cryptography schemes are based on it taking time to factor large numbers, but this is not the same thing as finding prime numbers. The basic principle is that if I take two large prime numbers, P1 and P2, and give you their product, Q, then it will take you a very long time to learn P1 and P2 unless I give you one of them. It is actually very important that the hardness of that problem does not come from the difficulty of finding prime numbers. Which numbers are prime is a question that is independent of breaking any particular key, which means that if that were the source of hardness, you could reuse the work from breaking one key to break future keys, by storing a list of the prime numbers you calculated. This would be a Bad Thing. There are a lot of misconceptions, in fact, about hardness, prime numbers, and factorization. People often assume that primality testing and factorization are equivalent, and that both are NP complete. In fact, PRIMES is known to be in P, and (the decision version of) integer factorization is probably not NP complete (it is in NP by way of PRIMES being in P), although it is not known if it is in P.