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

辗转相除法

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

{ax+by=gcd(a,b)(b  mod a)x+ay  =  gcd(a,b)(a  mod(b  mod a))x+(b  mod a)y  =  gcd(a,b)((b  mod a)  mod(a  mod(b  mod a)))x+(a  mod(b  mod a))y=gcd(a,b)\begin{cases} ax+by=\mathrm{gcd}\left( a,b \right)\\ \left( b\,\,\mathrm{mod}\ a \right) x+ay\,\,=\,\,\mathrm{gcd}\left( a,b \right)\\ \left( a\,\,\mathrm{mod} \left( b\,\,\mathrm{mod} \ a \right) \right) x+\left( b\,\,\mathrm{mod}\ a \right) y\,\,=\,\,\mathrm{gcd}\left( a,b \right)\\ \left( \left( b\,\,\mathrm{mod}\ a \right) \,\,\mathrm{mod} \left( a\,\,\mathrm{mod} \left( b\,\,\mathrm{mod} \ a \right) \right) \right) x+\left( a\,\,\mathrm{mod} \left( b\,\,\mathrm{mod} \ a \right) \right) y=\mathrm{gcd}\left( a,b \right)\\ \end{cases}

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

gcd(b  mod a,a)=gcd(ak+r,a)=gcd(r,a)\mathrm{gcd}\left( b\,\,\mathrm{mod} \ a, a \right) =\mathrm{gcd}\left( ak+r,a \right) =\mathrm{gcd}\left( r,a \right)

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

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

{a′=b  mod ab′=a\left\{ \begin{array}{c} a\prime=b\,\,\mathrm{mod} \ a\\ b\prime=a\\ \end{array} \right.

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

{x=0y=1a=0b=gcd(a,b)\begin{cases} x=0\\ y=1\\ a=0\\ b=\mathrm{gcd}\left( a,b \right)\\ \end{cases}

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

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

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

回溯

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

{ax+by=gcd(a,b)(b  mod a)x′+ay′=  gcd(a,b)\begin{cases} ax+by=\mathrm{gcd}\left( a,b \right)\\ \left( b\,\,\mathrm{mod} \ a \right) x\prime+ay\prime =\,\,\mathrm{gcd}\left( a,b \right)\\ \end{cases}

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

(b  mod a)x′+ay′=(b−⌊ba⌋a)x′+ay′=a(y′−⌊ba⌋x′)+bx′=gcd(a,b)\left( b\,\,\mathrm{mod}\ a \right) x\prime+ay\prime=\left( b-\lfloor \frac{b}{a} \rfloor a \right) x\prime+ay\prime=a\left( y\prime-\lfloor \frac{b}{a} \rfloor x\prime \right) +bx\prime=\mathrm{gcd}\left( a,b \right)

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

{x=y′−⌊ba⌋x′y=x′\left\{ \begin{array}{c} x=y\prime-\lfloor \frac{b}{a} \rfloor x\prime\\ y=x\prime\\ \end{array} \right.

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

所以 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