a^n mod m (with large n)

[Romulas]

Now, the problem I'm having is with the equation a^n mod m, where n happens to be very large. In this case, a^n will be computed before being reduced by mod m, so the calculations can be very strenuous.

However, Maple has a convenient &^ operator for reducing a^n along the way. It is used as a&^n mod m. This is much more efficient and saves much computation when attempting to mod by m.

I am a confused as to how an algorithm can be constructed to simulate the effects of the &^ operator. Maple Help doesn't have a name for it, so I couldn't really do a good search. Does anyone have some good references?

[axn]

google "modular exponentiation"

[Romulas]

Originally Posted by axn

google "modular exponentiation"

Awesome! Thanks for the quick reply!

[Raman]

mod_pow(a,n,m)
If n=1 then return a (mod m)
Else If n is even, then return mod_pow(a²,n/2,m)
Else If n is odd, then return a*mod_pow(a²,(n-1)/2,m)

O(log n) time only it takes for that process

Hint:
aⁿ (mod m)
Keep a variable X = a for iteration i=1
Write n in binary
Start with product = 1
For each bit of n from right to left,
(
if that bit = 1 then product = product * X
if that bit = 0 then don't change product
square X
)