20100508, 18:46  #1 
Apr 2010
19 Posts 
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? 
20100508, 19:03  #2 
Jun 2003
12434_{8} Posts 
google "modular exponentiation"

20100508, 19:24  #3 
Apr 2010
10011_{2} Posts 

20100508, 20:11  #4 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
4E9_{16} Posts 
mod_pow(a,n,m)
If n=1 then return a (mod m) Else If n is even, then return mod_pow(a^{2},n/2,m) Else If n is odd, then return a*mod_pow(a^{2},(n1)/2,m) O(log n) time only it takes for that process Hint: a^{n} (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 ) 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Bug with particular large number  VolMike  YAFU  18  20120409 21:39 
48bit large primes!  jasonp  Msieve  24  20100601 19:14 
NFS with 5 and 6 large primes  jasonp  Factoring  4  20071204 18:32 
Why only three large primes  fivemack  Factoring  18  20070510 12:14 
very large exponents  pacionet  Data  4  20051104 20:10 