【密码学基础】使用欧几里得算法求出RSA算法私钥d

用C++递归实现UP所讲解辗转相除法（程序很烂，仅供参考）

#include<bits/stdc++.h>

using namespace std;

bool f1=0;//用于判断函数是否第一次调用 

struct node //用于存储函数生成的d,k 

{

unsigned long long d;

unsigned long long k;

bool f;

};

node fd(

unsigned long long e,

unsigned long long r)

{

//用于找到合适的私钥d 

if(f1==1)//如果不是第一次调用 

{

//辗转相除 

if(e>r)e%=r;

else r%=e;

if(e==1)

//假设k=0

return {1,0,0};

if(r==1)

//假设d=1

return {1,e-1,1};

}

else f1=1;

node rfd=fd(e,r);

if(rfd.f==0)

return {rfd.d,((e*rfd.d-1)/r),1};//计算上一个r 

if(rfd.f==1)

return {((1+r*rfd.k)/e),rfd.k,0};//计算上一个e

}

int main()

{

//按顺序输入e,r两个参数 

unsigned long long e,r;

cin>>e>>r;

unsigned long long d;

d=fd(e,r).d;

//输出生成的d以及判断d是否合法 

cout<<"d="<<d<<endl;

cout<<"判断:"<<((d*e)%r==1)<<endl;

system("pause > nul");

return 0;

}