今天给各位分享模指数快速算法c语言的知识，其中也会对指数运算c语言进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
1、关于模乘的算法2、在C语言中，一个数字的摸是怎么计算的3、求一个高效的指数取模运算算法
关于模乘的算法
RSA算法中用到的大数运算
C. 大数的运算
1. 大数的运算原理
RSA算法依赖于大数的运算，目前主流RSA算法都建立在512位到1024位的大数运算之
上，所以我们首先需要掌握大数（比如1024位）的运算原理。
大多数的编译器只能支持到32位（或64位）的整数运算，即我们在运算中所使用的
整数必须小于等于32位，即0xFFFFFFFF，这远远达不到RSA的需要，于是需要专门建
立大数运算库，来解决这一问题。
最简单的办法是将大数当作字符串进行处理，也就是将大数用10进制字符数组进行
表示，然后模拟人们手工进行“竖式计算”的过程编写其加减乘除函数。但是这样
做效率很低。当然其优点是算法符合人们的日常习惯，易于理解。
另一种思路是将大数当作一个二进制流进行处理，使用各种移位和逻辑操作来进行
加减乘除运算，但是这样做代码设计非常复杂，可读性很低，难以理解也难以调试
。
这里我们采用了一种介于两者之间的思路：将大数看作一个N进制数组，对于目前的
32位系统而言，N可以取2的32次方，即0x100000000，假如将一个1024位的大数转化
成0x10000000进制，它就变成了32位，而每一位的取值范围是0－0xFFFFFFFF。我们
正好可以用一个无符号长整数来表示这一数值。所以1024位的大数就是一个有32个
元素的unsigned long数组。而且0x100000000进制的数组排列与2进制流对于计算机
来说，实际上是一回事，但是我们完全可以针对unsigned long数组进行“竖式计算
”，而循环规模被降低到了32次之内，并且算法很容易理解。
但考虑到乘法和除法，都要进行扩展才能进行快速的计算（如果把除法变减法而不
扩展，速度将慢的无法忍受）。所以我们将N取2的16次方的，即0xFFFF。每一位用
unsigned short来表示，当进行乘除运算时，将short扩展成long，这是编译器所支
持的，所以运算起来，比较快。
在C语言中，一个数字的摸是怎么计算的
你好！模就是除以某个数的余数。比如5%2，可以这样来看5/2的余数1，而商（2）我们不用管，只要余数。你上面的哪个模是47，我们完全可以写一个程序来计算出来。看下面我写的程序#includestdio.h
void main()
{
int x=17955,i;
printf(“\n”);
for(i=47;i=17955;i++)
if(x%i==47)printf(“dengyu %d\n”,i);
}结果有很多，你执行一下，就可以看到结果了。
求一个高效的指数取模运算算法
由于一个整数的指数结果很大，可能远远超出计算机处理范围，故必须简化计算方式．这里采用快速取模方法.原理为：在4的5次方运算中，5能够化作2*2+1，这是因为5的2进制数为101．所以4的5次方运算便能写作((4)^2*1)^2*4,其中1表示的是4的0次方，^2表平方．再运用模的性质：(a*b)mod(m)=(amod(m)*bmod(m))mod(m),所以（4^5）mod(m)可先化为（((4)^2*1)^2*4）mod(m)，再化为（((4)^2mod(m)*1)^2mod(m)*4）mod(m)．举例子－－（4^5）mod(3)＝（((4)^2*1)^2*4）mod(3)＝（(1*1)^2mod(3)*4）mod(3)=（1*4）mod(3)＝1．该函数运行方式取于上述算法思想，首先将幂分解成2进制数，得到一个从幂的最低位数开始01组成的栈：分解b为2进制数．记录下分解成的位数z，构造栈
for(;b!=1;b=1)
{
z++;
if(b%2==0) l[z]=0;
else l[z]=1;｝
然后出栈进行＂（a^b）mod(c)＂的运算．这里用栈的原因是为了使幂的2进制数排列倒过来，实现最高位上的2进制数能够循环它的位数次，最低位上的2进制数只循环一次．每次的循环得到平方取模的值，一直到结束，取得一个值，即（a^b）mod(c)．
for(;z0;z–)
{
if(l[z]) y=(y*a%c)*(y*a%c)%c;
else y=y*y%c;
}
if(l[0]) y=(y*a%c);//最后次模
return y;
这是一个比较快的运算方法.
完整源程序：
//指数取模:a的b次方modc=x
_int64 mod(_int64 a,_int64 b,_int64 c)//(a)^bmod(c)//条件1：在rsa中ac,其它不用ac.条件2:ac互素
{
_int64 l[500],z=-1,y;
for(;b!=1;b=1)//分解b为2进制数．记录下分解成的位数z，构造栈l
{
z++;
if(b%2==0) l[z]=0;
else l[z]=1;
}
//a%=c;//如果一开始数就很大，先模一次,防止过大, 求逆
y=a*a%c;//第一次模
for(;z0;z–)
{
if(l[z]) y=(y*a%c)*(y*a%c)%c;
else y=y*y%c;
}
if(l[0]) y=(y*a%c);//最后次模
return y;
}
C#改写的，在vs.net 2005下调试通过：
/// summary
/// 指数取模:x=(a^b)%c （a的b次方mod）
/// 条件1：在rsa中ac,其它不用ac
/// 条件2:ac互素
/// /summary
private static long mod(long a, long b, long c)
{
long[] l = new long[500];
long z = -1, y;
for (; b != 1; b = 1)//分解b为2进制数．记录下分解成的位数z，构造栈l
{
z++;
if (b % 2 == 0)
l[z] = 0;
else
l[z] = 1;
}
//a%=c;//如果一开始数就很大，先模一次,防止过大, 求逆
y = a * a % c;//第一次模
for (; z 0; z–)
{
if (l[z]0) y = (y * a % c) * (y * a % c) % c;
else y = y * y % c;
}
if (l[0]0) y = (y * a % c);//最后次模
return y;
} (参考百度）
关于模指数快速算法c语言和指数运算c语言的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
微信扫一扫 
支付宝扫一扫 
