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

    Office_Shredder

    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

    rcgldr

    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.

    http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
     
    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

    rcgldr

    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.

    http://en.wikipedia.org/wiki/Euler's_totient_function

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Modular Mathematics
  1. Modular Multiplication (Replies: 0)

  2. 'or' in mathematics? (Replies: 9)

  3. Modular Inverses? (Replies: 8)

  4. Modular arithmetic (Replies: 5)

  5. Modular arithmetic (Replies: 7)

Loading...