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

Question

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?

Answer 1

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

Applied to your example:

base 614, exponent 7, modulus 2609

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