# Modular Mathematics

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?

Staff Emeritus
Gold Member
2021 Award
By rather large number do you mean like 10, or like 100000000?

Also is n big as well?

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:
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

• 1 person
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: