RSA算法中r无法满足e*r%t==1的问题p=47;q=59;t=(p-1)×(q-1)=2668;r是与t互质的数,并满足r

Question

RSA算法中 r 无法满足e*r%t ==1的问题
p=47;
q=59;
t=(p-1)×(q-1)=2668;
r是与t互质的数,并满足r

Answer 1

#include
#include
#include
unsigned __int64 GCD(unsigned __int64 a,unsigned __int64 b)
{
\x05if(b==0)
\x05\x05return a;
\x05return GCD(b,a%b);
}
/*
已知a、b,求x,满足a*x =1 (mod b)
相当于求解a*x-b*y=1的最小整数解
*/
unsigned __int64 Euclid(unsigned __int64 a,unsigned __int64 b)
{
unsigned __int64 m,e,i,j,x,y;
long xx,yy;
m=b;
e=a;
x=0;
y=1;
xx=1;
yy=1;
while(e)
{
i=m / e;
j=m % e;
m=e;
e=j;
j=y;
y*=i;
if(xx == yy)
{
if(x > y)
{
y=x - y;
}
else
{
y-=x;
yy=0;
}
}
else
{
y+=x;
xx=1 - xx;
yy=1 - yy;
}
\x05\x05x=j;
}
\x05if(xx == 0)
{
x=b - x;
}
\x05return x;
}
unsigned __int64 RandomRelativelyPrime(unsigned __int64 n)
{
\x05unsigned __int64 r;
\x05srand(time(NULL));
\x05do
\x05{
\x05\x05r=rand()%n;
\x05}while(GCD(r,n)!=1);
\x05return r;
}
int main(int argc,char *argv[])
{
\x05unsigned __int64 p=47;
\x05unsigned __int64 q=59;
\x05unsigned __int64 n=p*q;
\x05unsigned __int64 t=(p-1)*(q-1);
\x05unsigned __int64 e1=889/*RandomRelativelyPrime(t)*/;
\x05unsigned __int64 e2=Euclid(e1,t);
\x05printf("p=%I64d q=%I64d p*q=%I64d t=%I64d e1=%I64d e2=%I64d\n",p,q,n,t,e1,e2);
\x05return 0;
}