模指数运算的二进制算法_HHC2017

个人资料

微博

正文字体大小：大中小

模指数运算的二进制算法

(2012-06-12 14:28:58)

标签：

分类： algorithm

模指数运算：

exp(a,e)mod m。最后都转化为一系列的模乘法运算。提高模指数运算速度的有效方法是减少模指数运算中模乘法耳朵次数。以二进制算法为例：

设e=(e0 e1 e2 ...)2,即将e转化为二进制序列；

1 初始化，t=exp(a,e0);

2 遍历e的二进制序列

i=1;

t=t*t mod m;

if(ei==1) t=t*a mod m

i=i+1

3 输出t

C#代码如下：

private long modExpFun(long a, int e, long m)

{

//获取e的串

string eStr = Convert.ToString(e, 2);

//初始化

long t = 0;

char ss = eStr[0];

int n = Convert.ToInt32(eStr[0].ToString());

t = (long)Math.Pow((double)a, (double)n);

for(int i=1;i<eStr.Length;i++)

{

t = (t * t) % m;

if (Convert.ToInt32(eStr[i].ToString()) == 1)

{

t = (t * a) % m;

}

return t;

}

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report