C语言实现模重平方算法
文章目录
模重平方算法:(b为底数,p为模)
1.将指数化为二进制数
2.核心:
令a=1
对二进制数从地位至高位循环执行
(1)若二进制数当前位为1,a=(a*b)mod p
否则 a不变
(2)b=b^2 mod p
最后当所有位执行完后a为所求值以2^5 mod 7 举例计算
由后半部分蓝字可看出算法的原理即将2^5 mod 7 拆分成 (2^1 mod 7)*(2^4 mod 7) mod 7
对于大指数,即将很大的数如1234567890123转化为二进制数只有41位,大大减少mod运算的数量(若按顺序做需要做1234567890123次mod运算!)
算法的时间复杂度为log2(n),很小
C代码:
include<stdio.h>
include<math.h>
include<stdlib.h>
void decimaltobinary(long long index,int * binary_i);
long long MRSM(long long b,int * binary_i,long long p);
int main()
{
long long p,index,b;
scanf("%lld",&p);
scanf("%lld",&index);
scanf("%lld",&b);
int* binary_i=(int *)malloc(sizeof(int)*100);
decimaltobinary(index,binary_i);//十进制转二进制
printf("p的二进制位数为%d\n",binary_i[0]);
long long element = MRSM(b,binary_i,p);//模重平方计算 b^p mod p 值即为b关于p的逆元
printf("%lld\n",element);}
void decimaltobinary(long long index,int * binary_i)
{
int i=1;
int remainder;
while(index!=0)
{
remainder=index%2;
if(remainder==1) binary_i[i]=1;
else binary_i[i]=0;
index/=2;
i++;
}
binary_i[0]=i-1;}
long long MRSM(long long b,int * binary_i,long long p)
{
int k=1;//k表示二进制目前的位数
int a=1;
while(k<=binary_i[0])
{
if(binary_i[k]==1)
{
a=(a*b)%p;
}
b=(b*b)%p;
k++;
}
return a;}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论