Solve Large Exponent Modular Math Problem Easily

[LS1088]

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?

 

[Office_Shredder]

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

Also is n big as well?

 

[rcgldr]

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

 

[dkotschessaa]

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?

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

 

[rcgldr]

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).