euclid.cpp

欧几里德算法：非常实用的！经调试通过！源代码不需任何修改！

/////////RSA 欧几里得算法实现的哦～～～

#include <iostream>


using namespace std;
void modular_linear_equation_solver(int a, int b, int n); 
int ext_euclid(int a,int b,int &x,int &y);

void main(int argc,char ** argv)
{
int p ;
int q ;
int x;
int e;

cout << "输入RSA加密素数P和Q的值!" << endl;

cin >> p >> q;

cout << "p is :" << p <<endl << "Q is :" << q <<endl;

cout << "输入RSA加密的公开密钥E的值!" << endl;

cin >> e;

cout << "E is :" << e << endl;

x = (p-1) * (q-1);
modular_linear_equation_solver(e,1,x);
}


int extended_euclid(int a,int b,int &x,int &y)
/*
d=gcd(a,b)=ax+by (x,y可能为0或负数);
输入整数a、b，返回gcd(a，b)和对应等式ax+by中的x,y;
详细证明见《黑书》P63
*/
{
int t1,t2;
if (b==0)
{
x=1;
y=0;
return a;
}else
{
t1=extended_euclid(b,a%b,x,y);
t2=x;
x=y;
y=t2-(a/b)*y;
return t1;
}
}
void modular_linear_equation_solver(int a,int b,int n)
/*
ax≡b(mod n)或ax+ny=b的整数解
详解见《黑书》P64
*/
{
int d,x,y,e,i,t;
d=extended_euclid(a,n,x,y);
if (b%d>0)
{
cout << "No answer!" << endl;
}else
{
e=x*(b/d)%n;
if (e<0) e+=n;
for (i=0;i<d;i++)
{
   t=(e+i*(n/d))%n;
   cout << "密钥D是:" << t <<endl;
}
}
}