#include #include main(){int p,q,e,d,m,n,t,c,r,k; printf("请输入两个素数 p 和 q: ");for(k=0;k<100;k++){scanf("%d%d",&p,&q);if((Prime(p)==1)&&(Prime(q)==1)) //推断两个数是否为素数，不是的话重新输入 { n=p*q; break; } elseprintf("输入的不全是素数\n 请重新输入两个素数 p 和 q: ");} printf(" n 为 %d\n",n); t=(p-1)*(q-1); //求 n 的欧拉数 t printf(" t 为 %d\n",t); printf("请输入公钥 e: "); scanf("%d",&e); if(e<1||e>t||husu(e,t)){printf("e 与 t 不互素，请重新输入: "); scanf("%d",&e);} d=1; while(((e*d)%t)!=1) d++; //由公钥 e 求出私钥 d printf("经计算私钥 d: %d\n",d); printf("请输入明文 m: "); //输入要加密的明文数字 scanf("%d",&m); c=miquyu(m,e,n); printf("密文 m 为 %d\n",c); printf("请输入密文 c: "); //输入要解密的密文数字 scanf("%d",&c); m=miquyu(c,d,n); printf("明文 m 为 %d\n",m);}int Prime(int m) //推断 p q 是否为素数{ int i,k; if(m<2) return 0; k=sqrt(m); for(i=2;i<=k;i++) if(m%i==0)break; if(i>k)return 1; //素数返回 1 else return 0; //否则返回 0} int miquyu(int a,int b,int c)//幂的取余{ int r=1; b=b+1; while(b!=1){r=r*a; r=r%c; b--;} return r;}int husu(int x,int y) //推断公钥 e 与 t 的是否互素{int t; while(y) {t=x; x=y; y=t%y; } if(x == 1) return 0; //x 与 y 互素时返回 0 else return 1; //x 与 y 不互素时返回 1}
