1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular Mathematics

  1. Oct 21, 2013 #1
    I have encountered this problem in its general form: finding a^k mod n, where k is a rather large number. I have been researching on the internet for several hours but I still don't understand it well. Can anyone provide a detailed explanation as to how to solve this kind of problems?
  2. jcsd
  3. Oct 21, 2013 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    By rather large number do you mean like 10, or like 100000000?

    Also is n big as well?
  4. Oct 21, 2013 #3


    User Avatar
    Homework Helper

    Assuming that "n" is prime or that "a" and "n" are relatively prime, then there is some i where (a^i) mod n = 1. Once you find i, then you're looking for a^(k mod i) mod n.

    update You can find a^i by using the extended Euclid algorithm, but that doesn't really help.

    Last edited: Oct 21, 2013
  5. Oct 21, 2013 #4
    Yes, we really need to know how big K is. One that works if K is ont too huge is to start finding numbers a^j (mod n) and then multiply the results together to get your final number. For example (assume = means congruence here) using somewhat smaller numbers.

    Let's say I wanted 2^20 (mod 111). This is small enough to calculate (it's 70) but let's see how else I can find it:

    2^2 = 4 (mod 111 )

    Easy enough. But now let's square that result.

    2^4 = 4^2 = 16 (mod 111)

    Still nothing interesting, but let's square this result this:

    2^8 = 16^2 = 256

    But that's

    256 = 34 (mod 111)

    It's much easier now to square 34 than 256. So let's do this a few times.

    2^16 = 34^2 = 1156 = 46 (mod 111)

    Now by rules of exponents:

    2^20 = 2^(16+4)

    Which is equal to:

    = (2^16)*(2^4)

    And since we calculated those, this is:

    = (46*16) = 736 = 70 (mod 111)

    -Dave K
  6. Oct 21, 2013 #5


    User Avatar
    Homework Helper

    In addition to repeated squaring, another possible optimization is to find i where a^i mod b = 1, where i will be some integer less than b-1. By using interation it can be determined that 2^36 mod 111 = 1. This means that 2^(j x 36) mod 111 = 1, for any integer value j. This means you only have to determine 2^(k mod 36) mod 111, using repeated squaring.

    Rather than using iteration to find i, there is a Euler Totient function, which will produce i or a multiple of i, depending on a and b.


    Calling the totient function t(), then for b = 111, t(111) = t(3 x 37) = t(3) t(37) = (2) (36) = 72. This eliminates having to iterate to find i, but it may produce a multiple of the smallest possible i. The repeated squaring to produce a product of 2^(k mod 72) mod 111 won't take that many iterations.

    The worst case scenario is if b is prime, such as 109. The totient for b if prime is b-1, so t(109) is 108, and you'd have to use repeated squaring to calculate a^(k mod 108) mod 109. (for example, 107 = 1 + 2 + 8 + 32 + 64).
    Last edited: Oct 22, 2013
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook