在 C++ 中，扩展欧几里德算法的递归到底发生了什么？

Question

我知道什么是扩展欧几里得算法以及为什么在编程中使用它。这是一个非常有用的算法，用于查找数字的逆 modulo。我知道如何在 C++ 中实现它，这就是我在下面用 C++ 实现它的方式。

typedef pair<int, int> pii;

#define x first
#define y second

pii extendedEuclidean(int a, int b)
{
    if(b==0)
        return {a,0};
    else {
        pii d = extendedEuclidean(b, a%b);
        return {d.y, d.x - (d.y*(a/b))};
    }
}

现在，如果我想找到一个数字的倒数 modulo，例如 13，其中 mod 例如 1000007，那么我只需通过

调用此函数

pair<int, int> res = extendedEuclidean(13, 1000007);

那么结果就是

res.first

我的问题是为什么以及在这个递归中到底发生了什么？以及为什么它会产生正确的结果。

N.B: 这里gcd(a, b)必须为1.

Answer 1

欧氏算法计算一对数(a, b)的最大公约数（假设a>b）。它使用 a 和 b 的任何公约数也是 a-b 的公约数的观察结果。原因如下：

设d为除数。那么，对于整数k，a可以表示为a=d*k，对于整数l，可以表示为b=d*l。然后，a-b=d*k-d*l=d*(k-l)。 k-l 又是一个整数。因此，d 必须是 a-b.

的除数

该算法所做的是尽可能多地从较大的数字中减去较小的数字。这是a%b部分。例如。如果a = 25和b = 7，a%b=4就是a减去b3次后的结果。之后，新的 a 将小于 b。因此，您交换两个数字。这是您调用递归的部分：extendedEuclidean(b, a%b);

扩展的欧几里得算法做得更多。此外，它计算两个数字 x 和 y，因此 gcd(a, b) = x * a + y * b。这是如何完成的：

在最后一次迭代中，您最终得到 a'=gcd 和 b'=0。因此，您有 gcd=a' * 1 + b' * 0，其中 1 和 0 分别是 x' 和 y'。假设前一次迭代中的值为 a'' 和 b''。那么我们就知道了a'=b''和b'=a'' % b''。有了这个，我们发现 b'=a''-(a''/b'')*b'' （尽可能多地减去）。而我们可以修改

gcd = a' * x' + b' * y'
gcd = b'' * x' + (a''-(a''/b'')*b'') * y'
    = a'' * y' + b'' * (x' - y' * (a''/b''))

因此，新的 x''=y' 和 y''=x' - y' * (a''/b'')。这是你的 return 声明 return {d.y, d.x - (d.y*(a/b))};.

一个例子：

让a=25, b=7。第一遍计算列 a 和 b（从上到下）。这说明了递归调用。第二遍计算列 x 和 y（从下到上）。这说明 return 语句：

 a  | b            |  x   | y                     | means
----+--------------+------------------------------+---------------------
 25 |  7           |  2   | -1 - 2 * (25/7) = -7  | 1 = 2 * 25 - 7 * 7 
  7 |  25 % 7 = 4  | -1   |  1 + 1 * (7/4)  =  2  | 1 = (-1) * 7 + 2 * 4
  4 |  7 % 4  = 3  |  1   |  0 - 1 * (4/3)  = -1  | 1 = 1 * 3 - 1 * 3
  3 |  4 % 3  = 1  |  0   |  1 - 0 * (3/1)  =  1  | 1 = 0 * 3 + 1 * 1
  1 |  3 % 1  = 0  |  1   |  0                    | 1 = 1 * 1 + 0 * 0

所以你得到 1 = 2 * 25 - 7 * 7，其中 2 是结果的 .first，-7 是结果的 .second。如果我们在 mod 25，这将减少到：

1 == 2 * 0 - 7 * 7
1 == -7 * 7

因此，-7 == 18（即result.second）是7 (mod 25)的乘法逆元。请注意，我交换了输入以避免不必要的第一次迭代。否则就是result.first.

在 C++ 中，扩展欧几里德算法的递归到底发生了什么？

What exactly happens inside extended euclidean algorithm's recursion in c++?

c++

algorithm

math

recursion

number-theory