0

Why is $(g^b \bmod N)^a \bmod N = g^{a*b} \bmod N$ ?

Specifically: Why/how does the mod N in the round brackets disappear from the first expression $(g^b \bmod N)^a \bmod N$?

I know of the exponential law that $g(^a)^b$ is equal to $g^{a*b}$ but I just do not understand why the $\bmod n$ in the round braces just disappears. Can someone help me with that? Has this anything to do with the exponential law or something entirely different?

Thanks in advance.

metamorphy
  • 39,111
user3542317
  • 3

1 Answers1

0

I assume that by $x \bmod N$, you mean the remainder when $x$ is divided by $N$. (Otherwise, the expression "$(g^b \bmod N)^a \bmod N$" is hard to interpret. Is the mod of a power of a mod a number? A residue class?)

The integer $g^b \bmod N$ differs from $g^b$ by some multiple of $N$. That is, $$g^b \bmod N = g^b + jN$$ for some integer $j$. For the same reason, $(g^b \bmod N)^a \bmod N$ differs from $(g^b \bmod N)^a$ by a multiple of $N$: $$(g^b \bmod N)^a \bmod N = (g^b \bmod N)^a + kN$$ for some integer $k$.

Putting these two equations together, $$(g^b \bmod N)^a \bmod N = (g^b + jN)^a + kN$$ If you expand $(g^b + jN)^a$, you get $(g^b)^a$ plus a lot of other terms that are all multiples of $N$, so $$(g^b \bmod N)^a \bmod N = (g^b)^a + mN$$ for some $m$. Therefore $$(g^b \bmod N)^a \bmod N = (g^b)^a \bmod N\,.$$

Kimmel
  • 55