0
$\begingroup$

I was reading on how Diffie-Helman works and the wikipedia article has the following:

$(g^a\;\mathrm{mod}\;p)^b\pmod p \equiv (g^b\;\mathrm{mod}\;p)^a\pmod p$

And that equation is true because of the $(g^a)^b=g^{ab}$ property. However what about the $\mathrm{mod}\; p$ part? Is it affected by exponentiation? If not what guarantees that at the end of the calculation both sides of the equation will be equal?

$\endgroup$
  • 1
    $\begingroup$ Every identity that is true without modulo is true with it. This has nothing to do with exponentiation. $\endgroup$ – M. Winter Jun 25 '18 at 9:52
  • $\begingroup$ @M.Winter Someone had edited the question and messed up the equation. Please view the updated one. $\endgroup$ – Konstantine Jun 25 '18 at 12:38
  • $\begingroup$ It seems you are about the change the meaning of your question after some answers were written. If you are interested in whether $(g^a)^b \;\mathrm{mod}\; p$ and $(g^a\;\mathrm{mod}\; p)^b\;\mathrm{mod}\; p$ give the same result, I recommend leaving your question as it is and asking another separate question. $\endgroup$ – M. Winter Jun 25 '18 at 12:44
  • $\begingroup$ The original question was with the equation as it is now. Someone edited for formatting reasons and forgot to add the $modp$ inside the exponentiation. $\endgroup$ – Konstantine Jun 25 '18 at 12:44
  • $\begingroup$ I see. This was unfortunate but not your mistake. I consider deleting or rewriting my answer then. $\endgroup$ – M. Winter Jun 25 '18 at 12:46
0
$\begingroup$

Speaken mathematically, $\mathrm{mod}\; p$ is a ring homomorphism from $\Bbb Z \to \Bbb Z/p\Bbb Z$, i.e. it preserves addition and multiplication. In less math slang, this means

$$ \def\cmod{\;\mathrm{mod}\;} \def\lmod{\mathrm{mod}\;} (a+b) \cmod p = (a\cmod p)+(b\cmod p)$$ $$(a\cdot b) \cmod p = (a\cmod p)\cdot (b\cmod p)$$

These are not too hard to check. But especially the second one is important for your case. Because this gives

\begin{align*} (g^a \cmod p)^b = \overbrace{(g^a \cmod p) \cdots (g^a \cmod p)}^{b\text{ times}} = \overbrace{(g^a)\cdots(g^a)}^{b\text{ times}} \cmod p = (g^a)^b \cmod p \end{align*}

Having this in place, we have

$$ (g^a \cmod p)^b =(g^a)^b \cmod p = (g^b)^a \cmod p =(g^b \cmod p)^a.$$

The second identitiy holds for the reason I already mentioned in the comments: if some identity holds without $\lmod p$, then also with $\lmod p$. And the same now gives

$$(g^a \cmod p)^b \equiv (g^b \cmod p)^a \pmod p.$$

$\endgroup$
0
$\begingroup$

Denote by $-\,\%\, n\colon \mathbb Z\to \{0,1,\dots,n-1\}$ the operation of taking the remainder when dividing by $n$. You want to show that $$ (ab)\,\% \,n = (a\,\%\,n) (b\,\%\,n)\,\%\,n. $$ Once this is shown, you can conclude that $$ (g^a)\,\%\, n = (g\,\%\,n)^p\,\%\,n. $$


In a more algebraic manner, you define $\%\,n$ in a different way: Denote by $\mathbb Z/n\mathbb Z$ the set of equivalence classes with respect to the relation $x\sim y$ if and only if $n$ dividides $x-y$. For example in $\mathbb Z/3\mathbb Z$ you have the equivalence class $$ [1] = \{ \dots, -8, -5, -2, 1, 4, 7, 10, 13, \dots \}. $$ Now you can define $a\,\%\,n$ to be the unique element in $[a]\cap\{0,1,\dots,n-1\}$. On $\mathbb Z/n\mathbb Z$ you now define addition and multiplication by \begin{align*} [a]+[b] &:= [a+b], \\ [a]\cdot[b] &:= [a\cdot b]. \end{align*} You need to show that these give well-defined operations, that is, the definitions are independent of the choice of representatives: when $a\sim a'$ and $b\sim b'$ you have $[a+b]=[a'+b']$ and $[ab]=[a'b']$.

Multiplication on $\mathbb Z/n\mathbb Z$ being well-defined then implies your statement about products and $\,\%\,n$.

$\endgroup$
  • $\begingroup$ You didn't read the question carefully. If amounts to the obvious $a=b\implies a\equiv b\mod p$. $\endgroup$ – Yves Daoust Jun 25 '18 at 10:06

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.