在RSA算法密钥产生过程中，设P=43,Q=17,取密钥D=593，求公钥

p=43
q=17
n=731
e1=593
e2=17

我是从1开始一个一个地试的.......

节选 http://baike.baidu.com/view/7520.htm

RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。
RSA的算法涉及三个参数，n、e1、e2。
其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。
e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2*e1)mod((p-1)*(q-1))=1。
(n及e1),(n及e2)就是密钥对。

公钥为17。具体计算如下：
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
//判断公钥e是否为素数，1成立，0不成立
int prime(int e);
//判断公钥e与(p-1)*(q-1)的最大公约数是否为1，1成立，0不成立
int gcd(int e,int pq);
//判断e*d余(p-1)*(q-1)是否为1，1成立，0不成立
int mod(int e,int d,int pq);
#define SIZE 1024
void main()
{
int p;
int q;
int e;//公钥
int d;//密钥
int pq;//(p-1)*(q-1)
int* eArray=(int*)malloc(sizeof(int)*SIZE);
int i=0;
int size;
printf("请输入素数p和q\n");
scanf("%d%d",&p,&q);
printf("请输入密钥d\n");
scanf("%d",&d);
pq=(p-1)*(q-1);
printf("p=%d\nq=%d\nd=%d(p-1)*(q-1)=%d\n",p,q,d,pq);
for(e=1;e<pq;e=e+2)
{
if(mod(e,d,pq)&&gcd(e,pq))
{
eArray[i]=e;
i++;
}
}
size=i;
printf("在0-%d可能的公钥数量为 %d \n",pq,size);
printf("公钥为:");
for(i=0;i<size;i++)
{
if(i%5==0)
printf("\n");
printf("%d ",eArray[i]);
}
printf("\n");
free(eArray);
}
int mod(int e,int d,int pq)
{
int ed=e*d;
if(ed%pq==1)
return 1;
return 0;
}
int gcd(int e,int pq)
{
if(prime(e)&&pq%e!=0)
return 1;
return 0;
}
int prime(int e)
{
for(int i=2;i<=int(sqrt(e)+1);i++)
{
if(e%i==0&&e!=2)
return 0;
}
return 1;
}

　　公钥为17。
　　#include <stdio.h>
　　#include <math.h>
　　#include <stdlib.h>
　　//判断公钥e是否为素数，1成立，0不成立
　　int prime(int e);
　　//判断公钥e与(p-1)*(q-1)的最大公约数是否为1，1成立，0不成立
　　int gcd(int e,int pq);
　　//判断e*d余(p-1)*(q-1)是否为1，1成立，0不成立
　　int mod(int e,int d,int pq);
　　#define SIZE 1024
　　void main()
　　{
　　int p;
　　int q;
　　int e;//公钥
　　int d;//密钥
　　int pq;//(p-1)*(q-1)
　　int* eArray=(int*)malloc(sizeof(int)*SIZE);
　　int i=0;
　　int size;
　　printf("请输入素数p和q\n");
　　scanf("%d%d",&p,&q);
　　printf("请输入密钥d\n");
　　scanf("%d",&d);
　　pq=(p-1)*(q-1);
　　printf("p=%d\nq=%d\nd=%d(p-1)*(q-1)=%d\n",p,q,d,pq);
　　for(e=1;e<pq;e=e+2)
　　{
　　if(mod(e,d,pq)&&gcd(e,pq))
　　{
　　eArray[i]=e;
　　i++;
　　}
　　}
　　size=i;
　　printf("在0-%d可能的公钥数量为 %d \n",pq,size);
　　printf("公钥为:");
　　for(i=0;i<size;i++)
　　{
　　if(i%5==0)
　　printf("\n");
　　printf("%d ",eArray[i]);
　　}
　　printf("\n");
　　free(eArray);
　　}
　　int mod(int e,int d,int pq)
　　{
　　int ed=e*d;
　　if(ed%pq==1)
　　return 1;
　　return 0;
　　}
　　int gcd(int e,int pq)
　　{
　　if(prime(e)&&pq%e!=0)
　　return 1;
　　return 0;
　　}
　　int prime(int e)
　　{
　　for(int i=2;i<=int(sqrt(e)+1);i++)
　　{
　　if(e%i==0&&e!=2)
　　return 0;
　　}
　　return 1;
　　}