(Update 1, 11/11/19: corrected a calculation error)
This is my first time asking a question here.
I was recently watching a video on crashcourse regarding cryptography, and an equation from Diffie–Hellman key exchange came up. The equation from video is :
$$ \left ( B^{x}\bmod C \right )^{y} = \left ( B^{y}\bmod C \right )^{x} = B^{xy}\bmod C $$
But that doesn't sound to be true. Infact, I tried replacing x,y with 2,3 and B,C with 3,7 , which makes the above statement as:
$$\left ( 3^{2}\bmod 7 \right )^{3} | \left ( 3^{3}\bmod 7 \right )^{2} | B^{2*3}\bmod 7$$
$$=\left ( 3^{2}\bmod 7 \right )^{3} | \left ( 3^{3}\bmod 7 \right )^{2} | 3^{2*3}\bmod 7$$
$$=\left ( 9\bmod 7 \right )^{3} | \left ( 27\bmod 7 \right )^{2} | 729 \bmod 7 $$
$$=( 2 )^{3} | ( 6 )^{2} | 1$$
But
$$ 8 \neq 36\neq 1$$
So how is that equation right? I thought that its probably because of the higher precedence of exponential over modular division will be the case and equation would be something like this when expanded:
$$ \left ( B^{xy}\bmod C^{y} \right ) = \left ( B^{yx}\bmod C^{x} \right ) = (B^{xy}\bmod C^{xy}) $$
But that also fails for last case, ie:
$$ \left ( 3^{6}\bmod 7^{2} \right ) = \left ( 3^{6}\bmod 7^{3} \right ) but \neq (3^{6}\bmod 7^{6}) $$
So what's the problem here? is the video claiming a wrong equation or my maths is wrong?
This is not a precedence problem; it is a problem of sloppy notation, and of a common conflation of two different notions, especially by computer scientists.
See this previous answer.
Basically, there are two notions:
The equivalence relation “congruent modulo $C$”, denoted $a\equiv b\pmod{C}$. This is a relation between integers $a$ and $b$, and it holds if and only if $C|a-b$, which turns out to be equivalent to “$a$ and $b$ have the same remainder when divided by $C$”. Like any equivalence relation, it induces a partition on the integers into equivalence classes, and $a\pmod{C}$ denotes the equivalence class of $a$ modulo $C$, which contains all integers that are congruent to $a$ modulo $C$.
The binary relation “modulo”, often denoted by % in computer languages. Here, “$a\bmod C$“ (or $a\% C$) means “the remainder when dividing $a$ by $C$”. It is usually the unique integer $r$, $0\leq r\lt |C|$ such that $a=qC+r$; sometimes, it is chosen to lie between $-\frac{|C|}{2}$ and $\frac{|C|}{2}$ instead. But in any case, this is a binary operation, which is how you interpreted it.
Computer scientists are often sloppy, conflating the two. The statement would be correct for the binary modulo operator if you reduce after exponentiation: $$(B^x\bmod C)^y\bmod C = (B^y\bmod C)^x\bmod C = B^{xy}\bmod C.$$
Alternatively, it can be a statement about congruences: $$(B^x)^y\equiv (B^y)^x \equiv B^{xy}\pmod{C}.$$
So you are correct that taking it literally it is incorrect as given.
Note that your final computation is incorrect, though. Taking $C=7$, $B=3$, $x=2$, and $y=3$, we have: $$\begin{align*} (B^x\bmod C)^y &= (3^2\bmod 7)^3 = (9\bmod 7)^3\\ &= 2^3 = 8.\\ (B^y\bmod C)^x &= (3^3\bmod 7)^2 = (27\bmod 7)^2\\ &= 6^2 = 36.\\ B^{xy}\bmod C &= 3^{6}\bmod 7 = 729\bmod 7\\ &= 1. \end{align*}$$ (because $729\bmod 7 = 1$, not $43$).
So you are right that $8$ is not equal to $36$ and is not equal to $1$. But you may note that $8\equiv 36\equiv 1\pmod{7}$, and if you take one more modulo operation, $8\bmod 7 = 36\bmod 7 = 1$ giving you the desired equality.