#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
unsigned long cd,ce;
unsigned long high_exp(unsigned long x,unsigned long y,unsigned long n)/*高次幂求模*/
{
unsigned long e,f;
f=x%n;
while(y!=1)
{
e=x*f;
f=e%n;
y--;

}
return(f);
}
unsigned long pr_num()/*产生素数*/
{
unsigned long c,a,b,i;

while(c!=0)
{ c=0;
a=random(10);
if(a==0) continue;
for(i=2;i<=sqrt(a);i++)
{
b=a%i;
if(b==0)
c++ ;
}
}

}
unsigned long gcd(unsigned long a,unsigned long d)/*欧几里得算法,是不是互素*/
{
unsigned long r;
while(r>0)
{
r=a%d;
a=d;
d=r;
}
if(a==1) return 1;
else return 0;
}
unsigned long widen_gcd(unsigned long x,unsigned long y,unsigned long*a1,unsigned long*a2,unsigned long*b1,unsigned long*b2)/*扩展欧几里的算法,*/
{
unsigned long a,b,q,r;

q=x/y ;
r=x%y ;
a=*a2-q*(*a1);
b=*b2-q*(*b1);
if(0==r)
{
return y ;
}

*a2=*a1 ;
*b2=*b1 ;
*a1=a ;
*b1=b ;
return widen_gcd(y,r,a1,a2,b1,b2);

}
unsigned long prod_ek_dk()/*产生密钥*/
{
unsigned long de,e,c,d,p,q,n,t,b1,b2,a2;
e=0;a2=1;b1=1;b2=0;
p=pr_num();

q=pr_num();
printf("p=%ld,q=%ld",p,q);
n=p*q;
/*printf("\n n=%ld",n);*/
t=(p-1)*(q-1);
printf("\n t=%ld",t);
do
{
d=random(t);
c=gcd(t,d);
}while(d==1||!c);
printf("\n d=%ld",d);

de=widen_gcd(d,t,&e,&a2,&b1,&b2);

if(de<0)
{
de=de+t;

}
printf("\n e=%ld",de);
cd=d;
ce=de;
return(n);
}

void main()
{
unsigned long f,c,n,d,e,ww,qq;
randomize();
n=prod_ek_dk();
d=cd;
e=ce;
printf("\n n=%ld",n);
printf("\n d=%ld e=%ld",d,e);
ww=5;
c=high_exp(ww,d,n);
printf("\n c=%ld",c);
qq=high_exp(c,e,n);
printf("\n qq=%ld",qq);
getch();
}
分开的各个模块经测试都是对的