system
Given the following post, respond as if you're commenting on Reddit:
human
If factoring numbers with ~1000 digits is so difficult that it is used in encryption, how do we know of primes with many millions of digits?

I know that certain cryptographic systems use large prime factorizations as their encryption method because it takes a long time to factor large numbers, and using numbers with 1000+ digits produces an encryption that is nigh-unbreakable with current technology.

So how is it that the largest known prime has over 20 million digits and we know of many prime numbers with millions of digits, if factoring numbers is so difficult?
gpt
They are different problems.

Finding out whether a number is prime is relatively easy. In CS-speak, if you have a number, you can determine whether it is prime in an amount of time that is polynomial in the size of the number. And there are even easier ways to just "find a big prime number."

The prime factor problem is totally different. The prime factor problem is, "Here is a huge number. You can take exactly two prime numbers out of the VAST collection of primes smaller than this huge number and multiply them together to get this number. Which two primes are the right ones?"

For a very large number n, there are approximately n/ln(n) primes smaller than n.

To check all the pairs of primes that can add up to your huge number X, you can check each prime Ai up to sqrt(X), then check if X/Ai = Bi is a prime. 

So, for a 1000 (binary) digit number, we have to check all the primes up to sqrt(2^1000) = 2^500.

There are approximately 2^500 / ln(2^500 ) = 2^491 primes smaller than 2^500 .

2^491 is about the same as 6*10^147. Good luck checking that many possibilities. Maybe you'll get lucky. (You won't.)

There MIGHT be an efficient algorithm for this problem, but no one has found one for it or any other problem like it. It's just that no one has ever proven there can't be an efficient algorithm.