Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.