# Easy way to calculate $614^7 \pmod{2609}$?

We are starting to go over Cryptography in our Number Theory class and we are doing an example of encrypting a message using something similar to RSA method.

I have I need to find what $$614^7 \pmod{2609}$$ is and I was wondering if there are little techniques or things that I could do to compute this say just with paper, pencil, and a basic scientific calculator?

I have started by saying $614=2\cdot307$ and then seeing if I can break $614^7=2^7\cdot307^7$ into some smaller pieces, example something like $307\cdot2^3=2456\equiv -153 \pmod{2609}$ which doesn't seem that helpful, but this has been the kind of method I am attacking this problem with right now. Or is this about the only kinds of method?

-
With small powers, is useful to write: $614^7=(614^2)^2\cdot614^2\cdot614$ and calculate separately $\mod 2609$ –  Dennis Gulko Apr 28 '13 at 10:21

You could make use of the following algorithm as explained here:

function modular_pow(base, exponent, modulus)
result := 1
while exponent > 0
if (exponent mod 2 == 1):
result := (result * base) mod modulus
exponent := exponent >> 1
base = (base * base) mod modulus
return result


base 614, exponent 7, modulus 2609


The while loop is executed three times, because 7 is binary 111. The result is 795.

-