Prime Numbers

- September 1, 2019

Prime Number

If a number cannot be divided into equal parts (other than parts of 1), then it's a prime number. Let's take two prime numbers, 97 and 103. It's relatively easy to verify that they are prime. By doing a primality test, we can determine that 97 and 103 are primes in a polynomial time, which means the complexity is limited. 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. That is because finding the unique prime dividers of a number takes an exponential time as the number grows. 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. What's even better is that Alice can prove that she possesses that information, without revealing 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.