system
Given the following post, respond as if you're commenting on Reddit:
human
ELI5: Prime numbers and encryption. When you take two prime numbers and multiply them together you get a resulting number which is the “public key”. How come we can’t just find all possible prime number combos and their outputs to quickly figure out the inputs for public keys?
gpt
The number of all possible prime number combos is simply too large.

Public key encryption relies on asymmetric mathematical operations - operations that take much, much longer to perform in one direction than the other.

Prime factorization is one of those. 12503 and 16187 are both prime numbers. If we multiply them - something you can do manually in less than a minute and in nanoseconds on a computer - we get 202,386,061.

Now try to factor that number without knowing what the prime factors are. The most basic method - a sieve - involves just running through prime numbers from 2 to the square root of your number and seeing if there are divisors.

The number of prime numbers less than 12503 is approximately 12503 / ln(12503) = 1325. So to factor our number, you'd need to do 1325 divisions vs. 1 multiplication to create it in the first place.

Moreover, as you create larger and larger numbers, this disparity between time-to-encode and time-to-decode grows without limit. No matter how large of a prime you pick to start, you'll never need more than a single multiplication - but you'll need an increasing number of divisions the larger the number goes.

Note: There are ways to make prime factorization more efficient, the sieve is just the easiest to explain.