View Single Post
Old 2010-05-08, 18:46   #1
Romulas
 
Apr 2010

238 Posts
Default 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?
Romulas is offline   Reply With Quote