Have you seen the lesson on Modern Cryptography? At the last checkpoint this was the most popular question asked by users:
In the lesson we saw how prime factorization played a fundamental role in the construction of mathematical locks. A mathematical lock (or one-way function) requires a procedure which is easy to perform and hard to reverse.
For example, If I randomly pick two large prime numbers such as: P1 = 709 and P2 = 733
and multiply them to get: N = P1 * P2
N = 709 * 733 = 519697 (this is easy to compute)
I end up with two things: a large number (519697) and the prime factorization for that large number (709 * 733)
Now, imagine I hide the prime factorization and only provide you with the following:
519697 = ? * ? (this is hard to compute)
If I ask you to find the prime factorization, where would you begin? Don't worry, everyone would struggle with this problem! To find the solution you must do a bunch of trial and error tests. Multiplication is fast (easy) to compute while prime factorization is slow (hard). This simple fact forms the basis for the RSA encryption scheme.
click here to see an animated graph demonstrating this difference
Though before going any further, we need to zoom in on the first step and ask ourselves an important question. When we say "randomly pick two large primes", how do we do this quickly? Is it an easy problem?
If you think about it for a while, you'll eventually agree that this step requires, at minimum, the ability to check if a randomly generated number (such as 99194853094755497) is prime or composite. Do you have a button on your calculator to tell you this?
I don't see one….Why is this?
To find out, let's begin with a challenge...