# Modular exponentiation commutativity in Diffie-Hellman

I've been learning about Diffie-Hellman key exchange.

One of the main tricks comes down to a commutativity property of exponentiation in the relevant modular arithmetic, it seems.

Something like:

(EDIT: As noted by @Ted, I got the formula wrong, hence my confusion.)

$$r^{A^B} \equiv r^{AB} \equiv \; ... \; \equiv r^{B^A} \pmod p$$

I know that this is not true in general, so presumably derives from the particular choices of r, A, B, and p.

I've done a fair amount of searching around, but cannot find a proof, or even a reasonable explanation of where this property arises from.

Can anyone here help?

• It is true for all integers r,A,B and p – Mayank Deora Dec 18 '15 at 2:45
• @MayankDeora: How about r=2, A=2, B=3, p=1000? I get $2^{2^3} \equiv 2^8 \equiv 256 \pmod {1000} \ne 2^{3^2} \equiv 2^9 \equiv 512 \pmod {1000} \ne 2^{3*2} \equiv 2^6 \equiv 64 \pmod {1000}$ – jwd Dec 18 '15 at 3:40
• @jwd You have the order of operations wrong. The relevant identity for Diffie-Helman is $(r^A)^B = (r^B)^A$, not $r^{(A^B)} = r^{(B^A)}$. – Ted Dec 18 '15 at 3:43
• @Ted: Ohhhhh (: Thank you. – jwd Dec 18 '15 at 3:46
• @jwd i have proved the identity as told by Ted – Mayank Deora Dec 18 '15 at 5:00

We have to prove that$$({r^A}modp)^B mod(p)=(r^Bmodp)^A mod(p)=(r)^{BA} modp$$ We would use binomial expansion for it.
Let $r=xp+y$ then $(r)modp=y$
As we know that:-$$r^A=(xp+y)^A=nC_0(y)^A+nC_1(xp)(y)^{A-1}+........+nC_n(xp)^A$$ If we calculate mod p of the above term we would get $(y^A)modp+0$
so,$(r^A)modp=(y^A)modp$ now let $y^A=\alpha p+\beta$ then $(y^A)modp=\beta$ ,now we have:-
$$((r^A)modp)^Bmodp=((y^A)modp)^Bmodp=(\beta)^Bmodp$$ Now we would calculate$(r^{AB}modp)$ $$r^{AB}modp=(xp+y)^{AB}modp=y^{AB}modp=(y^A)^Bmodp=(\alpha p+\beta)^Bmodp=(\beta)^Bmodp$$ i.e.$$((r^A)modp)^Bmodp=(r^{AB})modp=((r^B)modp)^Amodp$$ -Hence proved
• This is fine and all, but wouldn't it be simpler to note that (${r^A})^B = {r^A}\cdot{r^A}\cdot{r^A}\ldots = r^{A+A+A\ldots} = r^{A\cdot B}$ ? – jwd Dec 18 '15 at 17:13