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.

Thanks in advance.

  • 1
    $\begingroup$ 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). $\endgroup$
    – user26486
    Mar 23, 2015 at 18:53
  • $\begingroup$ You can't do it, I'm afraid. $\endgroup$
    – TonyK
    Mar 23, 2015 at 19:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.