int gcd(int f) //f=c=(a1-1)*(b1-1);
{
int x1=1,x2=0,x3;
int y1=0,y2=1,y3;
for(int i1=2;i1<f;i1++)
{
x3=f; //f=c=(a1-1)*(b1-1);
y3=i1;
int q=x3/y3;
int t1=x1-q*y1;
int t2=x2-q*y2;
int t3=x3-q*y3; //这条语句会一直都是0啊，y3怎么可能为1呢
x1=y1;
x2=y2;
x3=y3;
y1=t1;
y2=t2;
y3=t3;
if(y3==1)
{
return i1;
break;
}
}
}
这个函数在加密解密中起到什么作用
这个是扩展的欧几里得算法 用于求一个数的逆元
RSA中也就是知道公钥e 求私钥d
欧几里得算法是求最大公约数的，求逆元用扩展的欧几里得算法
原理：
如果gcd(a，b)=d，则存在m，n，使得d = ma + nb，称呼这种关系为a、b组合整数d，m，n称为组合系数。当d=1时，有 ma + nb = 1 ，此时可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。
int gcd(int a， int b ， int&； ar，int &； br)
{
int x1，x2，x3；
int y1，y2，y3；
int t1，t2，t3；
if(0 == a)
{//有一个数为0，就不存在乘法逆元
ar = 0；
br = 0 ；
return b；
}
if(0 == b)
{
ar = 0；
br = 0 ；
return a；
}
x1 = 1；x2 = 0；x3 = a；
y1 = 0；y2 = 1；y3 = b；
int k；
for( t3 = x3 % y3 ； t3 ！= 0 ； t3 = x3 % y3)
{
k = x3 / y3；t2 = x2 - k * y2；t1 = x1 - k * y1；
x1 = y1；x1 = y2；x3 = y3；
y1 = t1；y2 = t2；y3 = t3；
}
if( y3 == 1)
{ //有乘法逆元
ar = y2；
br = x1；
return 1；
}
else
{ //公约数不为1，无乘法逆元。这个是存在逆元的充要条件
ar = 0；
br = 0；
return y3；
}
}
核心是
for( t3 = x3 % y3 ； t3 ！= 0 ； t3 = x3 % y3)
{
k = x3 / y3；t2 = x2 - k * y2；t1 = x1 - k * y1；
x1 = y1；x1 = y2；x3 = y3；
y1 = t1；y2 = t2；y3 = t3；
}
一共有三行
x1 ，x2 ，x3
y1 ，y2 ，y3
t1 ，t2 ，t3
每次循环第三行都是算出来的 然后 把第一行y的值放到x t的值放到y
这三行都满足一个共同的性质
第一个数*a+第二个数*b=第三个数
比如x1*a+x2*b=x3
每次循环问题都会简化，距离结果更进
直到
当最终t3迭代计算到1时，有t1× a + t2 × b = 1，显然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。
最后坦白一点 今天我回答了3个RSA的问题 所以这个关于欧几里得的算法的解释 是我复制以前我回答他们的 也就是我抄袭的是自己的 当然这个算法不是我发明的
RSA中也就是知道公钥e 求私钥d
欧几里得算法是求最大公约数的，求逆元用扩展的欧几里得算法
原理：
如果gcd(a，b)=d，则存在m，n，使得d = ma + nb，称呼这种关系为a、b组合整数d，m，n称为组合系数。当d=1时，有 ma + nb = 1 ，此时可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。
int gcd(int a， int b ， int&； ar，int &； br)
{
int x1，x2，x3；
int y1，y2，y3；
int t1，t2，t3；
if(0 == a)
{//有一个数为0，就不存在乘法逆元
ar = 0；
br = 0 ；
return b；
}
if(0 == b)
{
ar = 0；
br = 0 ；
return a；
}
x1 = 1；x2 = 0；x3 = a；
y1 = 0；y2 = 1；y3 = b；
int k；
for( t3 = x3 % y3 ； t3 ！= 0 ； t3 = x3 % y3)
{
k = x3 / y3；t2 = x2 - k * y2；t1 = x1 - k * y1；
x1 = y1；x1 = y2；x3 = y3；
y1 = t1；y2 = t2；y3 = t3；
}
if( y3 == 1)
{ //有乘法逆元
ar = y2；
br = x1；
return 1；
}
else
{ //公约数不为1，无乘法逆元。这个是存在逆元的充要条件
ar = 0；
br = 0；
return y3；
}
}
核心是
for( t3 = x3 % y3 ； t3 ！= 0 ； t3 = x3 % y3)
{
k = x3 / y3；t2 = x2 - k * y2；t1 = x1 - k * y1；
x1 = y1；x1 = y2；x3 = y3；
y1 = t1；y2 = t2；y3 = t3；
}
一共有三行
x1 ，x2 ，x3
y1 ，y2 ，y3
t1 ，t2 ，t3
每次循环第三行都是算出来的 然后 把第一行y的值放到x t的值放到y
这三行都满足一个共同的性质
第一个数*a+第二个数*b=第三个数
比如x1*a+x2*b=x3
每次循环问题都会简化，距离结果更进
直到
当最终t3迭代计算到1时，有t1× a + t2 × b = 1，显然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。
最后坦白一点 今天我回答了3个RSA的问题 所以这个关于欧几里得的算法的解释 是我复制以前我回答他们的 也就是我抄袭的是自己的 当然这个算法不是我发明的
温馨提示：答案为网友推荐，仅供参考
