如果事先不了解 欧几里得算法 ,请点击。
扩展欧几里得算法:对于不完全为0的非负整数 a,b,必然存在整数对 X,Y,使得 aX + bY = gcd(a,b)。
解法见注释。
/*
How to solve "aX + bY = gcd(a,b)" ?
1、if b=0,
gcd(a,b) = a,
X = 1 , Y is any number.
For convenience,we make Y equals 0.
2、if b!=0,
gcd(a,b) = aX1 + bY1;
gcd(b,a%b) = bX2 + (a%b)Y2;
----> (a-a/b*b)Y2;
--> aX1 + bY1 = aY2 + b(X2-a/b*Y2);
--> X1 = Y2 , Y1 = X2-a/b*Y2;
So we can use recursion to sovle it.
*/
#include <stdio.h>
int GCD;
void ExGcd(int a,int b,int &x,int &y)
{
if(b == 0)
{
x = 1;
y = 0;
GCD = a;
return ;
}
ExGcd(b,a%b,x,y);
int t = x;
x = y;
y = t - a/b*y;
}
int main()
{
int a,b,x,y;
scanf("%d%d",&a,&b);
ExGcd(a,b,x,y);
printf("gcd(%d,%d) -> %d * %d + %d * %d\n",a,b,a,x,b,y);
return 0;
}
下面讨论如何用扩展欧几里得算法解决不定方程 aX + bY = c。
1、当 c mod gcd(a,b) = 0 的时候,该方程才有整数解。
2、方程可转化为 aX + bY = gcd(a,b) * c/gcd(a,b)。
等价于 aX/(c/gcd(a,b)) + bY/(c/gcd(a,b))= gcd(a,b)。
所以将方程 aX + bY = gcd(a,b) 的解乘以 c/gcd(a,b) 即可得到解 X0,Y0。
对于上述两个方程的其他解,我们可以用方程 a(X0+△X) + b(Y0+△Y) = c 表示。
于是得到 a△X + b△Y = 0,即 △X / △Y = - b/a = - ( b/gcd(a,b) ) / ( a/gcd(a,b) ) = t。( t 为与X、Y无关的参数)
于是方程的所有解可以用 X = X0 + b/gcd(a,b)*t , Y = Y0 - a/gcd(a,b)*t 来表示。
另外有一个没有证明过的猜想:利用上述方法求出的 (X0,Y0) 是所有 |X| + |Y| 的值中最小的(并不一定唯一),从而有X0 < |b|。(假设a < b)
分享到:
相关推荐
扩展欧几里得算法求逆元
此为扩展欧几里得算法求乘法逆元的完整程序,图形界面,使用 vc6.0 完成,完全标准正式的格式,绝对值10积分,有完整的代码,请使用 vc6.0 打开 DSW 工程文件,然后就可完全执行。
欧几里德算法和扩展欧几里德算法,经典算法系列
当a,b,且a互质时,计算ax+by=1的值, 是计算RSA密钥的基本步骤之一。
扩展欧几里德算法 欧几里德算法 代码 不可多得的资源
matlab的M函数文件,附带了函数的使用说明了
欧几里得是数论中的一个最初步的概念,它用来判断两个数的最大公因子,扩展的欧几里得能够进一步实现在两个数互素情况下的乘法可逆元。求可逆元是一些算法的基础。
本算法实现了用扩展欧几里得的方法求最大公因子和模逆元的方法,可以直接运行。
欧几里德算法和扩展欧几里德算法--透彻理解 模P乘法逆元 对于整数a、p,如果存在整数b,满足a×b mod p =1,则说,b是a的模p乘法逆元。
欧几里德算法和扩展欧几里德算法.doc
实现扩展欧几里得算法的代码,很简单,能够成功运行。
RSA扩展欧几里德算法算例,说明RSA密钥计算过程.
扩展欧几里得求逆-扩展欧几里得算法求乘法逆元
欧几里德算法和扩展欧几里德算法。用C和C++实现。.zip
acm 扩展欧几里德算法与中国剩余定理ppt教程 acmer教程系列 acm 扩展欧几里德算法与中国剩余定理ppt教程 acmer教程系列 很详细的讲解哦!
35扩展欧几里得算法1
介绍了扩展欧几里得算法的实现代码,有需要的朋友可以参考一下
就是扩展欧几里德算法
MATLAB实现的扩展欧几里得算法