# How can I verify the result of modular exponentiation

I ask a computer to calculate $x^y \pmod z$, where $x,y,z$ are all large numbers. How can I verify the correctness of the result returned by the computer.

I assume that I myself cannot afford expensive computations. The most expensive calculation I can do is multiplication of two large numbers. And I cannot do it too many times.

• You can try using classic modular arithmetic tricks and you may get lucky to have the expression simple to calculate. If $z$ is prime, then if $z\not\mid x$ (otherwise trivially the answer is $0$), then $x^y\equiv x^{y\pmod{z-1}}\pmod{z}$. If $z$ is composite, then you can use Euler's theorem, or Carchimael function (which is stronger), but only if $(x,z)=1$. Otherwise use Chinese Remainder Theorem by splitting $z$ into prime factors and using either trivially $x^y\equiv 0\pmod{p_i}$ if $p_i\mid x$ or Fermat's Little Theorem (special case of Euler's Theorem, used in the begin. of the comment). Mar 23, 2015 at 18:53