a^n mod m (with large n)
 

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?

google "modular exponentiation"

[quote=axn;214396]google "modular exponentiation"[/quote]
Awesome! Thanks for the quick reply!

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

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

Hint:
a[sup]n[/sup] (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
)