Prime Numbers

-

Photo by Tony Hand on Unsplash

The building blocks of numbers

If a number is the product of two or more numbers, then it's a composite numbers. If not, then it's a prime number. For example, you can write 10 as a product of 2 and 5. But you cannot write 7 as the product of other numbers. 2*3 = 6 , 2*4 = 8, 3*3 = 9. As such, 7 is a prime number.

Every number is either a prime or can be built by multiplying primes together. Multiplying prime numbers generate all other numbers, which by definition are composite. As such, we can see primes as the building blocks of numbers: composites are only a "byproduct". 10 is the byproduct of 2 and 5. The prime number 7, on the other hand, builds with other prime numbers the following numbers: 14, 21 and so on.

Prime assertion

A primality test checks whether a number is prime or not. It must check whether the number is the product of other numbers. This is the same as to check whether other numbers can divide it.

This process is relatively easy as it is done in a non-exponential time, in a polynomial time. The AKS method runs in polynomial time and provides a definitive answer.

Prime factorization

Prime factorization is the process of finding prime numbers that, by being multiplied with each other, give birth to the resulting composite number.

This process is relatively hard as it is done in an exponential time. It cannot be brute-forced as for now.

Difficulty asymmetry use

Let's take two prime numbers, 97 and 103. It's relatively easy to verify that they are prime through a primality test. The product, 9991, is extremely easy to compute (97 * 103).

On the other hand, if we take the number 9991 while not knowing that's it's the product of 97 and 103, it's difficult to get that information back. If the number is big enough, it's actually practically impossible. Plus, 9991 is magnitudes bigger than 97 or 103.

Alice knows the dividers of 9991 (97 and 103), because she picked 97 and 103 herself. Others don't know which prime numbers Alice picked. Alice can even prove that she possesses that information without revealing it (97 and 103). She'll be the only person to solve in a reasonable time a problem related to 9991, by using 97 and 103. Everyone can verify that her answer solves the problem, even if they don't have access to the numbers 97 and 103. She'll have proven that she possess the information without leaking it, because she used 97 and 103 as a key to unlock a difficult problem.

Let's say that 9991 is a house, and 97 and 103 are the keys of the house. Alice can prove she is the owner of the house by using the key to open the door. Others will see that she opened the door, and therefore know for sure that she is the owner. It is a public and verifiable information.

Private Key and Public Key

97 and 103 could be the private key and 9991 the public key. We generate the public key from the private key. This process is easy. We cannot easily generate the the private key from the public key, that process is computationally impractical, in other words impossible. This difficulty asymmetry can be used in Private - Public key cryptography.