#include <stdio.h>
#include <math.h>
int Prime(int m)
{
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;
else
return 0;
}
int PowerMod(int a, int b, int c) {
int ans = 1;
a = a % c;
while(b>0)
{
if(b % 2 == 1)
ans = (ans * a) % c;
b = b/2;
a = (a * a) % c;
}
return ans;
}
int husu(int x,int y)
{
int t;
while(y)
{ t=x;
x=y;
y=t%y;
}
if(x == 1)
return 0; else
return 1;
}
int eular(int n) //欧拉函数
{
int number = 1, i;
for(i=2; i*i <= n; i++)
{
if(n%i == 0)
{
n /= i;
number *= (i-1);
while(n%i == 0)
{
n /= i;
number *= i;
}
}
}
if(n > 1)
{
number *= (n-1);
}
return number;
}
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;
}
else
printf("输入的不全是素数\n请重新输入两个素数 p 和 q: ");
}
printf(" n 为 %d\n",n);
t=(p-1)*(q-1);
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=PowerMod(e, eular(t)-1, t); //由公钥e求出私钥d
printf("经计算私钥 d: %d\n",d);
printf("请输入明文 m: "); //输入要加密的明文数字
scanf("%d",&m);
c=PowerMod(m,e,n);
printf("密文m为 %d\n",c);
printf("请输入密文 c: "); //输入要解密的密文数字
scanf("%d",&c);
m=PowerMod(c,d,n);
printf("明文 m 为 %d\n",m);
}
