高速冪乗

$f,n,m$ が比較的大きい数であっても、 $f^n \mod m$ を手早く計算できます。 ruby のプログラムを置いておきましょう。

# a* f^n mod  m
def mypow1(a,f,n,m)
   while (1==1) do
       if (n==0) 
          return(a % m)
       end
       if (n==1)
         return((a*f) % m)
       end
       n1 =n.div(2)
       r1 = n % 2
       if (r1 == 1)
           a=a * f
       end
       f=(f*f) % m
       n=n1  
   end
end
##################################################################
# mypow(f,n,m) 
# returns
# f^n mod m
##################################################################
def mypow (f, n,m)
return(mypow1(1,f,n,m))
end