Let's revisit prime numbers and modular arithmetic. Prime numbers are unique because they cannot be expressed as the product of two smaller integers. And modular arithmetic is simply what it sounds like—wrapping a number around a clock, or modulus.
Let's take a number and wrap it around a modulus. We will choose the number 42 and wrap it around the modulus 12.
42 wraps around 12 three times, with 6 left over. So we say our result is 6. Now let's do the same operation, but choose a prime modulus. And this time, let's write it using multiplicative modular group notation. We'll use the small prime 23. Let our group be \((Z_{23})^{x}\). This group consists of the set of integers relatively prime to 23 under multiplication modulo 23. If we want to solve for \(3^{3}\) - we compute this and get 27. Then we divide it by 23. Our remainder is 4. So, we say that \(3^{3}\) is congruent to 4 for group \(Z_{23}\).
There are multiple solutions for this example. And using Fermat's Little Theorem, we can show that there are sometimes infinitely many solutions for various others.
Fermat's Little Theorem tells us that if p is prime, then for any integer a, \(a^{p} - a\) is an integer multiple of p. If a is not divisible by p, then we can say that \(a^{(p-1)}\) is congruent to 1 modulo p. Essentially, this is a primality test. And one we can use to prove inductively that there are infinite solutions in some cases.
Fermat's little theorem states that if p is prime and a is not divisible by p, then the following equation is the case:
\(a^{(p-1)} \equiv 1 \pmod{p}\)
If one wants to test whether p is prime, then we can pick random integers a not divisible by p and see whether the congruence holds. If it does not hold for a value of a, then p is composite. This congruence is unlikely to hold for a random a if p is composite. Therefore, if the equality does hold for one or more values of a, then we say that p is probably prime.
Let's consider an equation with many possible solutions. Let's say we are tasked with solving for x in the following equation:
We are looking for integer solutions \(x\) that satisfy this congruence. And if we calculate various powers of 2 modulo 7, we can see a pattern emerge:
\[ \begin{align*} 2^1 &\equiv 2 \mod 7 \\ 2^2 &\equiv 4 \mod 7 \\ 2^3 &\equiv 1 \mod 7 \\ 2^4 &\equiv 2 \mod 7 \\ 2^5 &\equiv 4 \mod 7 \\ 2^6 &\equiv 1 \mod 7 \\ \end{align*} \]The powers of 2 repeat in a cycle of length 3 (1, 2, 4) modulo 7. We already see that, in this context, calculating powers of 2 , there are multiple inputs which forge the same output. This is in part due to residue classes and the uniform distribution.
Let's take a closer look with how Fermat's Little theorem plays a role in this. We start with the original congruence equation:
Raise both sides to 3:
\[ (2^x)^3 \equiv 3^3 \pmod{7} \]Simplify:
\[ 2^{3x} \equiv 27 \pmod{7} \]Here, we use Fermat's Little theorem: if \(p\) is a prime number and \(a\) is an integer not divisible by \(p\), then \(a^{p-1} \equiv 1 \pmod{p}\). In this case, \(p = 7\), and since 2 is not divisible by 7, we have \(2^{7-1} \equiv 1 \pmod{7}\). The 27 on the right side simplifies to 1:
Recall that \(2^3 \equiv 1 \mod 7\) too, - so we'll use this smaller form and raise both sides: \[ (2^3)^n \equiv 1^n \mod 7 \quad \Rightarrow \quad 2^{3n} \equiv 1 \mod 7 \]
Thus, any \(x\) of the form \(x = 3n\) where \(n\) is an integer will satisfy the congruence \(2^x \equiv 1 \mod 7\).
For example, let \(n = 1\) and \(x = 3\), then \(2^3 \equiv 1 \mod 7\). Similarly, when \(n = 2\) and \(x = 6\), then \(2^6 \equiv 1 \mod 7\). Both \(x = 3\) and \(x = 6\) are solutions to the equation \(2^x \equiv 1 \mod 7\), and there are infinitely many solutions of the form \(x = 3n\) (where \(n\) is any integer). So, 3, 6, 9, 12, and so on.
This uniform distribution of solutions in modular arithmetic means solutions are evenly spaced out within the particular residue class 1 mod 7, resulting in a predictable pattern of infinite possible solutions.
The prime number 7 of course is a silly example. And too small to be effective against attacks if it were used in a cryptographic system.
But it demonstrates a property we desire—a function that is easy to compute going forward, but difficult to reverse. The 'solving' of this is what is referred to as the discrete logarithm problem. And in a real world cryptographic system, we'd use a large prime—moduli that are thousands of bits long, e.g. 2048, 3072, 4096, 8192 bits—which drive up the computational difficulty needed to reverse and solve such a discrete logarithm. A large prime number in a cryptographic system could help drive the solving difficulty to hundreds or thousands of years, given current computing hardware.
The discrete logarithm problem is currently an unsolved problem in computer science. Can the discrete logarithm be computed in polynomial time on a classical computer? It seems the answer is .. not yet. Thus, this property guarantees us some security in context of cryptography. At least until the quantum computing apocalypse arrives.
No comments:
Post a Comment