If you're behind a web filter, please make sure that the domain *.kastatic.org is unblocked.

## Primality test

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