软讯网络 > 软件时空 > 软件相关 > 扩展欧几里得算法
【标 题】：扩展欧几里得算法
【关键字】：
【来 源】：http://www.cublog.cn/u/8780/showart.php?id=231659
扩展欧几里得算法
欧几里得算法中，计算 x, y 的最大公约数的方法是辗转相除，例如：
gcd (
26, 15)
26 % 15 = 1 ... 11
15 % 11 = 1 ... 4
11 % 4 = 2 ... 3
4 % 3 = 1 ... 1
3 % 1 = 3 ... 0
可知，gcd (26, 15) = 1
如果 gcd(x, y) = r，那么有 ax + by = r，可以看出，上面的步骤实际上是可以直接得出 a, b 的：
26 % 15 = 1 ... 11 => 11 = 26 - 15 1 1 -1
15 % 11 = 1 ... 4 => 4 = 15 - 11 = 15 - (26 - 15) = -26 + 2*15 1 -1 2
11 % 4 = 2 .. 3 => 3 = 11 - 4*2 = (26 - 15) - (-26 + 15) * 2 = 3*26 - 5*15 2 3 -5
4 % 3 = 1 ... 1 => 1 = 4 - 3 = (-26 + 2*15) - (3*26 - 5*15) = -4*26 + 7*15 1 -4 7
3 % 1 = 3 ... 0
在每一轮，我们都可以得到一个模的表达式为：ri = aix + biy
如果不考虑第一轮和第二轮，那么ai 和 bi 可以表示为(qi 为每一轮得到的商)：
ai = ai-2 - qi * ai-1
bi = bi-2 - qi * bi-1
现在来考虑第一轮和第二轮，按照上面的公式，可以认为
a-1 = 1, b-1 = 0
a0 = 0, b0 = 1
有了这两对预设值，上面的两个公式就成立了
求逆元，由上面可以看出，gcd(x, y) = 1 的时候
如果 ax + by = 1，那么 ax = -by + 1 => ax = 1 (mod b)
这时候，a 即是 x 的逆元
|
int gcd (int x, int y, int *a1, int *a2, int *b1, int *b2)
{
int q, r, a, b;
q = x / y;
r = x % y;
a = *a2 - q*(*a1);
b = *b2 - q*(*b1);
if (0 == r) {
return y;
}
*a2 = *a1;
*b2 = *b1;
*a1 = a;
*b1 = b;
return gcd (y, r, a1, a2, b1, b2);
}
|
【相关文章】
没有相关文章
|