分治法写算法！！！

Question

设计算法求解a^n mod m,其中a>1,n是一个大整数。如何处理a^n的巨大数量级？

Answer 1

int n = 5,a=3,m=14,i=2;
            double t = a%m;
            Dictionary <int, double> store = new Dictionary<int,double >  ();
            for (; i < n+1; )
            {                
                store.Add(i/2, t);               
                t*=t;
                t = t % m;
                i += i;
            }
            i /= 2;
            while  (i != n)
            {                
                for (int j = store.Count-1; j >= 0; j--)
                { 
                    if(store.Keys.ElementAt (j)+i<n+1)
                    {
                        i += store.Keys.ElementAt(j);
                        t =t * store.Values.ElementAt (j);
                        t=t    %m ;
                    }
                }
            }            Console.ReadKey();