1. C语言基础
  2. 乘法逆元
  3. 信息安全算法基础
  4. 操作系统基础
  5. x86汇编基础
  6. 信息论与编码

辗转相除法

先温习辗转相除法和裴蜀等式：

为什么右边都等于 gcd(a,b) 呢，因为

当 相同时，k 取任何整数都是成立的。

上面的过程本质上就是两个数 a, b，开始互相迭代

而这样迭代的结果必然会出现下面的情况：

需要注意，每次迭代后 x, y 的值都不同了。

以上都是辗转相除法的内容，也就是得到最大公因数的过程。但是之前的关注点在于如何得到最后的 a 或者 b，但是现在的关注点在于 x, y 如何得到。我们知道最终迭代的结果可以得到 x, y 的值，那么我们只需要回溯就可以了。

当 a, b 置换，上面的式子也可以写成对称的形式。

回溯

如何回溯呢，可以通过引用机制，也就是传入指针或者引用，这样伴随着函数的返回，值也修改了。具体修改的规则怎么确定呢？这就需要一点儿数学知识了，对于：

第二个式子可以等价的写成：

也就是说每一次辗转相除之前和之后的 x, y 满足下面的关系：

也就是说每次回溯的时候应该按照上面的式子，修改之前的值。

所以 C++ 程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//最大公约数
int gcd(int a, int b) {
    if (a % b == 0) {
        return b;
    } else {
        int t = a;
        a = b;
        b = t % b;
        return gcd(a, b);
    }
}

void extgcd(int a, int b, int &x, int &y) {
    if (a == 0) {
        x = 0, y = 1;
        return;
    }
    extgcd(b % a, a, x, y);
    int t = x;
    x = y - b / a * x;
    y = t;
}

int euclid_mod_reverse1(int a, int n) {
    //检查输入合法
    if (gcd(a, n) != 1 || a <= 0 || n <= 0) {
        return -1;
    }

    int x, y;
    extgcd(a, n, x, y);
    return (n + x % n) % n;
}

Haskell 的程序或許更加直观：

1
2
3
4
5
6
7
8
9
10
11
12
modInverse :: Int -> Int -> Maybe Int
modInverse a n = case gcd a n of
  1 -> Just $ makePositive $ fst $ extgcd a n
  _ -> Nothing
  where
    extgcd 0 b = (0, 1)
    extgcd a b =
      let (x', y') = extgcd (b `mod` a) a
          x = y' - (b `div` a) * x'
          y = x'
      in (x, y)
    makePositive x = if x >= 0 then x else x + n