如何用代码实现这个算法

Answer 1

很困了，懒得再调了，LZ自己试试吧。using System;
using System.Collections.Generic;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int m = 79;
            int e = 51;
            int n = 90;            Console.WriteLine("Result = " + ExpMod(m, e, n));
            Console.ReadLine();
        }        public static int ExpMod(int m, int e, int n) // ((m^e) mod n)
        {
            List<bool> split = SplitExp(e);
            if (split.Count == 0)
            {
                return 1;
            }            int result = -1;
            int mod = 1;
            for (int i = 0, j=0; i < split.Count; i++, j++)
            {
                if (j == 0)
                {
                    mod = Mod(m, n);
                }
                else
                {
                    mod = MultiMod(mod, mod, n); // (m^(2^j)) mod n
                }
                Console.WriteLine(string.Format("({0}^(2^{1})) mod {2} = {3}", m, j, n, mod));                if (split[i])
                {
                    if (result == -1)
                    {
                        result = mod;
                    }
                    else
                    {
                        result = MultiMod(result, mod, n);
                    }          
                }
                //Console.WriteLine("by now, result is " + result);
            }
            return result;
        }        private static List<bool> SplitExp(int e)
        {
            if (e <= 0)
            {
                return new List<bool>();
            }
            List<bool> bits = new List<bool>();
            do
            {
                if (Mod(e, 2) != 0)
                {
                    bits.Add(true);
                }
                else
                {
                    bits.Add(false);
                }
                e = e >> 1;
            } while (e != 0);
            return bits;
        }        private static int MultiMod(int m1, int m2, int n) // (m1 * m2) mod n
        {
            return Mod(Mod(m1, n) * Mod(m2, n), n);
        }        private static int Mod(int m, int n)
        {
            return m % n;
        }
    }
}
显示结果如下：
(79^(2^0)) mod 90 = 79
(79^(2^1)) mod 90 = 31
(79^(2^2)) mod 90 = 61
(79^(2^3)) mod 90 = 31
(79^(2^4)) mod 90 = 61
(79^(2^5)) mod 90 = 31
Result = 19

Answer 2

或者用这样的递归，不过可能会造成堆栈溢出。private static int MultiMod(int m, int e, int n)
{
    if (m % n == 0)
    {
        return 0;
    }    if (e == 1)
    {
        return m % n;
    }    return ((m % n) * fun(m, e - 1, n)) % n;
}