This is about … .
Say, we have a number 10 and another number 2. Say, we raise 2 to different powers and perform mod operation on the result. What would the result be?
| Power | Result (2^power mod 10) |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 6 |
| 5 | 2 |
| 6 | 4 |
| 7 | 8 |
| 8 | 6 |
| 9 | 2 |
| 10 | 4 |
So, we see the pattern: 2, 4, 8, 6 repeating over and over.
Now imagine we need to generate the number randomly. But we won’t get that with these numbers, obviously. Which numbers do we use? This is where prime magic comes into play. Let’s take 3 and 17 instead and see for ourselves:
| POWER | RESULT (3^Power MOD 17) |
|---|---|
| 1 | 3 |
| 2 | 9 |
| 3 | 10 |
| 4 | 13 |
| 5 | 5 |
| 6 | 15 |
| 7 | 11 |
| 8 | 16 |
| 9 | 14 |
| 10 | 8 |
| 11 | 7 |
| 12 | 4 |
| 13 | 12 |
| 14 | 2 |
| 15 | 6 |
| 16 | 1 |
| 17 | 3 |
No pattern here though. That the beauty of prime numbers. That’s not the only magical thing about them, but that an improtant one to understand when dealing with cryptography. Although, an important note. The base number does not neccessarily needs to be a prime, but it needs to be the primitive root of the prime number used for the modulus operation. What’s a primitive root?
❗️Not all numbers have primitive roots. Only numbers that are powers of a prime number or twice the power of a prime number have primitive roots. For example, prime numbers and numbers that are twice a prime number (like 2, 4, 6, 10, 14) have primitive roots. For a given prime number p, there may be multiple primitive roots, but finding one is computationally intensive. However, once a primitive root is found for a specific prime number, it can be reused in cryptographic operations. ChatGPT
Now, not ANY prim number would dance this beautifully.