2
$\begingroup$

(a * b)$^{x}$ mod n = ((a$^{x}$ mod n) * (b$^{x}$ mod n)) mod n

Can anyone give me some tips to prove the above equation? Thanks.

$\endgroup$
2
$\begingroup$

This follows from basic modular arithmetic: if $k\equiv r\pmod{n}$ and $\ell\equiv s\pmod{n}$, then $k\ell\equiv rs\pmod{n}$. Since $(ab)^x = a^xb^x$, then what you have is just this instance with $k=a^x$, $\ell=b^x$, $r=a^x\bmod n$ and $s=b^x\bmod n$. The final "$\bmod n$" just assures that you fall inside the main residue class representatives.

$\endgroup$

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.