Prove equivalence of Diffie-Hellman shared secret How can I prove that:
$ (g^b \bmod{p})^a \bmod{p} = (g^a \bmod{p})^b  \bmod{p}$
where p is a prime number, g is a primitive root of p, and a and b are integers.
While I understand that $(g^b)^a = (g^a)^b$ , I cannot figure out how to deal with the mod functions...
 A: You can expand $(g^b \bmod p)$ as $g^b + pK$ by the definition of $\text{mod}$.
Then $(g^b + pK)^a = g^{ab} + \binom{a}{1}g^{(a-1)b}pK + \ldots + (pK)^a$
Since all but the first of the terms in the binomial expansion contain a factor of $p$, $(g^b \bmod p)^a \equiv g^{ab} \pmod p$
A: There is an additional restriction on the remaining terms of the binomial expansion posted above that no one has commented on yet. Starting from the above solution:
$$(g^b \bmod p)^a =(g^b +pK)^a = g^{ab}+{a \choose 1}g^{(a-1)b}pK+...+(pK)^a$$
And as mentioned previous, since p is a factor in all terms except the first in the expansion,
$$(g^b +pK)^a = g^{ab}+pQ$$
Where Q is generally some integer whose value comes from the remaining terms in the binomial expansion. In the original answer it is assumed that,
$$g^{ab} \bmod p = g^{ab}+pQ$$
And then,
$$(g^b \bmod p)^a = g^{ab}\bmod p$$
However, the above statement isn't generally true for any random integers g, p, a and b, and is not simply due to the rules of modular arithmetic.
It's only true when the value of Q is restricted by the fact that g is a primitive root modulo p. Intuitively it's because both $g^b \bmod p$ and $g^a \bmod p$ are coprimes of p, and when raised to an arbitrary power and then taking the modulus p, you will always get the same remainder.
It would be nice if someone could post a more formal proof of this as it has important implications in crytography.
Edit: above I mentioned that the coprimes are raised to an arbitrary power. This isn't strictly true, as in Diffie-Hellman key exchange, this power is the private key of each end user. The intuition is more like this: raising the coprime of p which was generated by a, when raised to the power b, gives the same result as raising the coprime of p which was generated by b, when raised to the power a. This causes the two initial coprimes to "go around the clock face" by the amount created by the other generator. This is a fundamental relationship for any pair of coprimes, generated by a primitive root modulo p.
