6
$\begingroup$

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...

$\endgroup$
6
$\begingroup$

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$

$\endgroup$
9
  • 1
    $\begingroup$ How g^b mod p = g^b + pK? $\endgroup$ Jul 25 '14 at 9:42
  • 1
    $\begingroup$ @codeomnitrix, $a \equiv b\pmod c$ is a shorthand notation for $\exists k : a - b = ck$ $\endgroup$ Jul 30 '14 at 9:34
  • $\begingroup$ are u sure about (g^b mod p)^a ≡ g^(ab) mod p? lets try with g = 2, a = 1, b = 3, p== 11 (2^3 mod 11) ^ 5 != 2 ^ (5*3) mod 11 as obviously 8^5 != 2^15 mod 11 $\endgroup$ Jun 30 '16 at 11:27
  • $\begingroup$ @DmitryMartovoi, I have no idea where your 5 came from, but yes, I am sure because I am completely convinced by the proof in the answer. I am also completely convinced that "8^5 != 2^15 mod 11" is obviously false: $8^5 = 2^{15}$ so there's no need to even compute the values mod 11. $\endgroup$ Jun 30 '16 at 11:33
  • 1
    $\begingroup$ @isquared-KeepitReal, yes, $K \in \mathbb{Z}$. I don't agree that I'm missing $\bmod p$ because that's $\equiv$ rather than $=$, but it would have been better to use $\pmod p$ rather than $\bmod p$ at the end of the last line. Possibly my TeX knowledge was deficient back in 2011. I have edited in the improvement. $\endgroup$ May 2 '18 at 16:08
0
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.