Don't like this style? Click here to change it! blue.css
You have this problem to solve, given \(g, h, p\) find the unknown \(x\) such that \(g^x = h\) mod \(p\).
We know, thanks to Fermat's little Theorem, that \(m^{p-1} = 1 \) mod \(p\) for any integer \(m\).
So we're interested in reducing the search space for \(x\) from \(1, \cdots, p-2\) to something much smaller.
The idea is that we can actually figure out \(x\) mod \(m\) for any \(m\) that divides \(p-1\)
When I go concrete I'll use \(p=31\) in the following to match the notes.
To show how that works let's play with \(x\) mod \(3\). Every integer can be written down as \(3k, 3k+1,\) or \(3k + 2\) for an arbitrary integer \(k\). This comes from when we looked at modular arithmetic as infinite sets, like \(3 \cdot \mathbb{Z} + 1\) as this big infinite set of all things that are 1 larger than a multiple of 3.
We don't know which of those 3 worlds \(x\) lives in but we could say that \(x = 3k + y\) where \(y\) is either 0, 1, or 2.
At this point maybe it seems a tad abstract but if we can change this problem from hunting for \(x\) inside the range \(1, \cdots, p-2\) to hunting for \(y\) in the range \(0,1,2\) we've certainly made a smaller problem.
OK NOW we're ready to play with the original equation: \(g^x = h\)
Let's replace \(x\) with \(3k + y\):
\(g^{3k + y} = h\)
We know that \(g^{p-1} = 1\). Now if 3 happens to divide \(p-1\) like in the \(p=31\) case then we have a trick we can use:
In our \(p=31\) case Fermat's little theorem gives \(g^{30} = 1\). So the big idea is that we can raise both sides of the main equation to the 10th power.
Watch what happens
\(g^{10 \cdot (3k + y)} = h^{10}\)
Playing with the left hand side we get:
\( g ^{10 \cdot (3k + y)} = g^{30k + 10y} = g^{30k} \cdot g^{10y} = (g^{30})^{k} \cdot g^{10y} = (1)^{k} \cdot g^{10y} = g^{10y} \)
So that means \(g^{10y} = h^{10}\)
Did we make progress?
Well now we have a simple search to do, look at \(g^0, g^{10}, g^{20}\) and compare those 3 values with \(h^{10}\) (all of this is mod 31)
So we calculate \(h^{10}\) and compare it with the three possible values of \(y\) and we KNOW that one of them will match up. Let's say when \(y=1\) for some specific value of \(h\) then it must be that \(g^{10} == h^{10}\) which would imply that \(x = 3k + 1\) for some value of \(k\). Now we know that the final answer will be 1 mod 3.
You can imagine that we could repeat this process for other factors of \(p-1\). When \(p=31\) that would mean 2, 3, 5.
But could the trick work for other moduli?
Like, no one is stopping us from writing down \(x = 7k + y\). So plug it in to the original equation: \(g^x = h\) We get \(g^{7k + y} = h\) But since 7 doesn't divide 30 we don't have some nice way to get rid of needing to find the \(k\) AND find the \(y\). Raising both sides to any power is never going to reduce my search space.
That is the heart of Pohlig-Hellman, for numbers \(m\) that divide \(p-1\) we can change the search space from \(m \cdot k + y\), (where \(y = x\) mod \(m\) ), to ignoring needing the \(k\) and only needing to find \(y\) which is ALOT less work.
After all of that use Chinese Remainder Theorem to finish the problem.
So we know that \(g^{p-1} = 1\) mod \(p\) for any non-zero integer \(g\) and any prime \(p\).
The next more general version of that is Euler's Theorem which says that for any modulus \(N\) (not necessarily prime) we have:
\(g^{\phi(N)} = 1\) mod \(N\)
DETAILED ASIDE: We actually know where this comes from, which is the size of the group made by non-zero integers mod \(N\) mixed with LaGrange's theorem (from our math week ages ago). It comes from the fact that any number with GCD 1 with \(N\) has a modular inverse and the rest don't. BUT we can ignore the origins and trust the theorem.
OK, Back to the narrative: \(g^{\phi(N)} = 1\) mod \(N\)
So my next question is, what is \(g^{\phi(N) + 1}\) mod \(N\) ???
Well \(g^{\phi(N) + 1} = g^{\phi(N)} \cdot g = 1 \cdot g = g\).
How about this one then: what is \(g^{2 \cdot \phi(N) + 1}\)???
OK let's play some more: \(g^{2 \cdot \phi(N) + 1} = (g^{\phi(N)})^{2} \cdot g = (1)^{2} \cdot g = 1 \cdot g = g\).
If you follow, you're probably easy to convince now that \(g^{k \cdot \phi(N) + 1} = g\) mod \(N\) for any integer value of \(k\).
THAT is the big idea behind RSA.
Take your plaintext message PT and convert it to an integer (as we've done many times) and call it \(m\) (for message).
Then take a large modulus \(N\) which is the product of two large primes \(p\) and \(q\).
Now publish \(N\) and a public exponent \(e\) (usually 65537). The cipher text \(c\) is \(m^e\) mod \(N\).
The big idea is that if someone knows \(\phi(N)\) which happens to be \((p-1)(q-1)\) they can calculate the modular inverse of \(e\) mod \(\phi(N)\) to get some \(d\) such that \(d \cdot e = k \cdot \phi(N) + 1\) for some integer \(k\).
Now that means that \( m ^{d \cdot e} = m ^ {k \cdot \phi(N) + 1} = (m^{\phi(N)})^{k} \cdot m^{1} = (1)^k \cdot m = m\).
So to decrypt \(c = m^e\) we just take it to the \(d\), the modular inverse of \(e\) modulo \(\phi(N)\). Thus \(c^d = m\) mod \(N\) and finding \(d\) takes knowing \(phi(N)\) which takes knowing how \(N\) factors into \(N = p \cdot q\). Since factoring giant numbers is expensive things are "safe".