a的b次方模n算法

2019-04-13 14:41发布

站内文章 / 模拟电子
13155 0 1248
当b好大时，使用该算法是最好的选择。常应用于密码学： 代码： /* File: abn.c Description: 求 a的b次方模n的通用算法 Author: hanxi */ #include #include int f(int a, int b, int n) { int c=0, d=1; int i; for (i=31; i>=0; i--) { d = (d*d) % n; c *= 2; int tmp; tmp = 1<<i; //printf("tmp=%d ",tmp); if ((b&tmp)!=0) { d = (d*a) % n; c++; } } return d; } int main() { int a = 2, b = 5, n = 10; printf("求a的b次方模n "); printf("请输入a,b,n（用逗号隔开，如果a,b,n全为0则退出系统）:"); scanf("%d,%d,%d",&a,&b,&n); printf("a=%d,b=%d,n=%d ",a,b,n); while (a!=0 && b!=0 && n!=0) { int d = f(a,b,n); printf("%d的%d次方模%d=%d ",a,b,n,d); int x = pow(a,b); printf("%d的%d次方模%d=%d ",a,b,n,x%n); printf("请输入a,b,b（用逗号隔开）："); scanf("%d,%d,%d",&a,&b,&n); printf("a=%d,b=%d,n=%d ",a,b,n); } printf("程序已结束..."); return 1; }

热门文章