If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content
Current time:0:00Total duration:2:58

Video transcript

over 2,000 years ago Euclid showed every number has exactly one prime factorization which we can think of as a secret key it turns out that prime factorization is a fundamentally hard problem let's clarify what we mean by easy and hard by introducing what's called time complexity we have all multiplied numbers before and each of us has our own rules for doing so in order to speed things up if we program a computer to multiply numbers it can do so much faster than any human can here is a graph that shows the time required for a computer to multiply two numbers and of course the time required to find the answer increases as the numbers get larger notice that the computation time stays well under one second even with fairly large numbers therefore it is easy to perform now compare this the prime factorization if someone told you to find the prime factorization of 589 you will notice the problem feels harder no matter what your strategy it will require some trial and error until you find a number which evenly divides 589 after some struggle you will find 19 times 31 is the prime factorization if you were told to find the prime factorization of 437,000 231 you'd probably give up and get a computer to help you this works fine for small numbers though if we try to get a computer to factor of larger and larger numbers there is a runaway effect the time needed to perform the calculations increases rapidly as there are more steps involved as the numbers grow the computer needs minutes then hours and eventually will require hundreds or thousands of years to factor huge numbers we therefore say it is a hard problem due to this growth rate of time needed to solve it so factorization is what Cox used to build the trapdoor solution step 1 imagine Alice randomly generated a prime number over 150 digits long call this p1 then a second random prime number roughly the same size call this p2 she then multiplies these two primes together to get a composite number n which is over 300 digits long this multiplication step would take less than a second we could even do it in a web browser then she takes the factorization of n p1 times p2 and hides it now if she gave n to anyone else they would have to have a computer running for years to find the solution step 2 Koch's need to find a function which depends on knowing the factorization of n for this he looked back to work done in 1760 by swiss mathematician Leonhard Euler