数论基础之模方程初步

扩展欧几里得算法
¶

问题描述
¶

已知 $a, b$ 为常整数，求方程 $a x + b y = gcd (a, b)$ 的一对整数解?

问题简析
¶

令 ${\begin{aligned} A = a \mod b \\ B = b \end{aligned}$ ，构造方程

\begin{array}{r} (1) & A X + B Y = gcd (A, B) . \end{array}

由于 $gcd (a, b) = gcd (a \mod b, b) = gcd (A, B)$ ，所以

\begin{aligned} a x + b y & = (a - ⌊ \frac{a}{b} ⌋ \times b + ⌊ \frac{a}{b} ⌋ \times b) \times x + b y \\ = (a - ⌊ \frac{a}{b} ⌋ \times b) \times x + (b y + ⌊ \frac{a}{b} ⌋ \times b x) \\ = (a (\mod b)) \times x + b \times (y + ⌊ \frac{a}{b} ⌋ \times x) \\ = A x + B \times (y + ⌊ \frac{a}{b} ⌋ \times x) \end{aligned}

因此有 ${\begin{aligned} X = x \\ Y = y + ⌊ \frac{a}{b} ⌋ \times x \end{aligned} \Rightarrow {\begin{aligned} x = X \\ y = Y - ⌊ \frac{a}{b} ⌋ \times X \end{aligned}$

方程 (1) 的构造与辗转相除有异曲同工之妙，需要说明的是， $gcd (x, 0) = x$ 。所以：

当 $b = 0$ 时，我们得到一组解 ${\begin{aligned} x = 1 \\ y = 0 \end{aligned}$
当 $b \neq 0$ 时，套用辗转相除的框架求出 $(X, Y)$ ，再得到 $(x, y)$ 。

程序实现
¶

1
2
3
4
5
6
7
8
9
10
11
typedef long long LL;
void extendEuclid(LL a, LL& x, LL b, LL &y, LL& d) { // d=gcd(a,b)
  if (!b) { 
    d = a;
    x = 1;
    y = 0; 
  } else { 
    extendEuclid(b, y, a%b, x, d);
    y -= (a / b) * x; 
  }
}

上述代码中，将 d = a 的执行顺序放在最前面是一个小技巧，因为这样就可以像下面这样调用函数，此时不需要预先将 $g c d (a, b)$ 求出来，而是在整个算法中顺带求出的：

1
2
3
extendEuclid(a, x, b, d, d);
// or
extendEuclid(a, d, b, d, y);

值得一提的是，扩展欧几里得算法解出的一组解是所有解中 $| x | + | y |$ 最小的；

问题扩展
¶

求方程 $a x + b y + c = 0$ 有多少对整数解，满足 $x \in [x_{1}, x_{2}], y \in [y_{1}, y_{2}]$ ？

由前文可知，当 $gcd (a, b) ∣ c$ 时，方程有解。因为方程 $a x + b y = gcd (a, b)$ 的解乘上 $\frac{c}{gcd (a, b)}$ 就是此方程的一组解。由此，我们可以推出 $a x + b y = k \cdot gcd (a, b)$ ，所以，当 $gcd (a, b) ∤ c$ 时，方程无解。

那有多少个解呢？

如果 $(x_{0}, y_{0}), (x_{1}, y_{1})$ 是方程的两个解，那么 $a (x_{1} - x_{0}) + b (y_{1} - y_{0}) \equiv 0$ .
令 $a^{'} = \frac{a}{gcd (a, b)}, b^{'} = \frac{b}{gcd (a, b)}$ ，显然， $gcd (a^{'}, b^{'}) = 1$
所以， $(x_{1} - x_{0}) ∣ b^{'}, (y_{0} - y_{1}) ∣ a^{'}$ ，并且 $\frac{x_{1} - x_{0}}{b^{'}} \equiv \frac{y_{0} - y_{1}}{a^{'}}$ 。
一般地，若 $(x_{0}, y_{0})$ 是方程 $a x + b y + c = 0$ 一组解，那么 $(x_{0} + k b^{'}, y_{0} - k a^{'})$ 也是一组解。其中， $b^{'} = \frac{b}{gcd (a, b)}, a^{'} = \frac{a}{gcd (a, b)}$ ， $k$ 为任意整数。

逆元
¶

对于任意整数 $A, N$ ，如果存在一个整数 $B$ 使得 $A \cdot B \equiv 1 \mod C$ ，那么， $A$ 和 $B$ 称作模 $C$ 意义下的互为逆元，记做 $A^{- 1} = B$ 或 $B^{- 1} = A$ 。

求解逆元
¶

如果 $gcd (A, N) = 1$ ，根据欧拉定理，有 $A^{- 1} = N^{φ (N) - 1}$ ，特别地，当 $N$ 是素数时， $φ (N) = N - 1$ 。另外，由于 $gcd (A, N) = 1$ ，构造方程 $A x + N y = 1$ ，用扩展欧几里得算法也可求出 $A$ 在模 $N$ 意义下的逆元 $A^{- 1} = x$ .
如果 $gcd (A, N) \neq 1$ ，由前文可知，方程 $A x + N y = 1 \neq k \cdot gcd (A, N)$ 不存在整数解，故不存在逆元。

程序实现
¶

欧拉定理求逆元。当 $N$ 是素数时， $φ (N) = N - 1$ ， $A$ 的逆元为 $A^{N - 2}$

inv.euler.cpp

1
2
3
4
5
6
7
8
9
10
11
12
typedef long long LL;
LL powerMod(LL A, LL x, LL mod) { // 返回 A^x%mod
  LL ans = 1;
  for(; x > 0; x >>= 1, A = A * A % mod) {
    if (x & 1) ans = ans * A % mod;
  }
  return ans;
}

LL inv(LL A, LL mod) {
  return powerMod(A, mod-2, mod);   
}

扩展欧几里得求逆元

inv.euclid.cpp

1
2
3
4
5
6
7
typedef long long LL;
LL inv(LL A, LL mod) {
  LL x, y, d;
  extendEuclid(A, x, N, y, d);
  // 若 A 和 mod 不互质，则不存在逆元
  return d == 1 ? x : -1;
}

中国剩余定理
¶

若正整数 $m_{1}, m_{2}, \dots, m_{k}$ 两两互素，且 $0 ⩽ a_{1} < m_{1}, 0 ⩽ a_{2} < m_{2}, \dots, 0 ⩽ a_{k} < m_{k}$ . 求下列同余方程组的整数解：

\begin{array}{r} (2) & \begin{aligned} x \equiv a_{1} (\mod m_{1}) \\ x \equiv a_{2} (\mod m_{2}) \\ \dots \\ x \equiv a_{k} (\mod m_{k}) \end{aligned} \end{array}

问题简析
¶

令 $w_{i} = \prod_{j \neq i} m_{j}$ ，显然有：

\begin{array}{r} (3) & gcd (w_{i}, m_{j}) = {\begin{aligned} 1, & i = j \\ m_{j}, & i \neq j \end{aligned} \end{array}

构造方程 $w_{i} x_{i} + m_{i} y_{i} = gcd (w_{i}, m_{i}) = 1$ 。那么，由方程组 (3) 有，

\begin{array}{r} (4) & w_{i} x_{i} (\mod m_{j}) \equiv {\begin{aligned} 1, & i = j \\ 0, & i \neq j \end{aligned} \end{array}

结合方程组 (2) 和方程组 (4)，进而有，

\begin{array}{r} (5) & a_{i} w_{i} x_{i} (\mod m_{j}) \equiv {\begin{aligned} a_{i}, & i = j \\ 0, & i \neq j \end{aligned} \end{array}

所以， $x = \sum_{i = 1}^{k} (a_{i} \cdot w_{i} \cdot x_{i})$ 为同余方程组 (2) 的解。更一般地，方程的解为

x = \sum_{i = 1}^{k} (a_{i} \cdot w_{i} \cdot x_{i}) + k \prod_{i = 1}^{k} m_{i}

剩下的问题仅需利用扩展欧几里得算法求出 $x_{i}$ 。

程序实现
¶

crt.cpp

1
2
3
4
5
6
7
8
9
10
LL crt(int N, int* a, int* m) {
  LL M = 1, ans = 0;
  for (int i = 0; i < N; ++i) M *= m[i];
  for (int i = 0; i < N; ++i) {
    LL w = M / m[i], x, y, d;
    extendEuclid(w, x, m[i], y, d);
    ans = (ans + x * w * a[i]) % M;
  }
  return ans;
}

Baby Step Gaint Step
¶

求一个整数 $x \in [0, C - 1]$ 使得 $A^{x} \equiv B (\mod C)$ 。其中， $C$ 为素数。

问题简析
¶

注意到 $C$ 是一个素数，那么对于任意 $X$ 都存在一个模 $C$ 意义下的逆元 $X^{- 1}$ ，使得 $X \cdot X^{- 1} \equiv 1 \mod C$ 。取任意正整数 $m$ ，如果事先知道所有的 $A^{x_{0}} \mod C, (0 ⩽ x_{0} < m)$ 的值，如何判断是否存在一个 $x^{'}$ 满足 $k m ⩽ x^{'} = x_{0} + k m < (k + 1) m$ ，使得 $A^{x^{'}} = A^{x_{0} + k m} \equiv B \mod C$ 成立呢？

注意到，令方程两边同乘以 $A^{k m}$ 的逆元 $A^{- k m}$ ，得到 $A^{x_{0}} \equiv B \cdot A^{- k m} \mod C$ 。所以，我们仅需将映射关系 $x_{0} \to f (x_{0}) = A^{x_{0}} \mod C, (0 ⩽ x_{0} < m)$ 存进哈希表或平衡树中，再从 $0 \sim m$ 枚举 $k$ 的值，对于每个 $k$ 检查哈希表或平衡树中是否存在 $B \cdot A^{- k m} \mod C$ ，若存在即可取得对应的 $x_{0}$ 的值。

$m$ 应该取多少合适呢？注意到这样做的时间复杂度是 $O (m + \frac{C}{m})$ 的 ^[1]，不难证明，当 $m$ 取 $\sqrt{C}$ 时复杂度最优。

程序实现
¶

bsgs.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef long long LL;
unordered_map<LL, int> emp;

int bsgs(LL A, LL B, LL C) {
  emp.clear();
  int M = ceil(sqrt(1.0 * C));

  LL AA = 1;
  for (int x0 = 0; x0 < M; ++x0) {
    if (!emp.count(AA)) emp[AA] = x0;
    AA = AA * A % C;
  }

  LL Am = inv(powerMod(A, M, C), C);
  for (int k = 0; k < M; ++k) {
    if (emp.count(B)) return emp[B] + k * M;
    B = B * Am % C;
  }
  return -1;
}

Extend Baby Step Gaint Step
¶

求一个整数 $x \in [0, C - 1]$ 使得 $A^{x} \equiv B (\mod C)$ 。其中， $C$ 为合数。

问题简析
¶

在分析之前，先看一个定理：若 $k \cdot A \equiv k \cdot B \mod k \cdot C$ ，则有， $A \equiv B \mod C$ .
这个定理不难证明，事实上，仅需构造方程 $k \cdot A - k \cdot B = k^{'} \cdot k \cdot C$ ，在等式两边同除以 $k$ 即可得证。

再回过头来看普通版的 Baby Step Gaint Step 是如何工作的。注意到， Gaint Step 能够成功走出去的前提是 $A^{m}$ 存在模 $C$ 意义下的逆元 $A^{- m}$ 。由前文可知， $A^{- m}$ 存在的充要条件为 $gcd (A^{m}, C) = 1$ ，此时必有 $gcd (A, C) = 1$ ^[2]。设 $G_{t} = gcd (A^{t}, C), C^{'} = \frac{C}{G_{t}}, D = \frac{A^{t}}{G_{t}}$ ，根据上面的定理，不难想到，我们只要找出某个整数 $0 ⩽ t < C$ 满足 $G_{t} = G_{t + 1}$ ，则上述方程可转化为

A^{x} = G_{t} \times \frac{A^{t}}{G_{t}} \times A^{x - t} = G_{t} \times D \times A^{x - t} C = G_{t} \times \frac{C}{G_{t}} = G_{t} \times C^{'}

不难发现， $D$ 和 $C^{'}$ 是互质的；因为 $G_{t} = G_{t + 1}$ ，所以 $A$ 和 $C^{'}$ 也是互质的 ^[3] 。

接下来讨论 $B$ 和 $G_{t}$ 的关系：

若 $G_{t} ∣ B$ ，结合前面给出的定理，有
$A^{x} \equiv B \mod C \Rightarrow D \cdot A^{x - t} \equiv \frac{B}{G_{t}} \mod C^{'}$
又因为 $D$ 和 $C^{'}$ 是互质的，所以存在模 $C^{'}$ 意义下的逆元 $D^{- 1}$ ；进一步将同余方程化为
$A^{x - t} \equiv (D^{- 1} \cdot \frac{B}{G_{t}}) \mod C^{'}$
由于 $A$ 和 $C^{'}$ 是互质的，根据前面的分析，直接套用普通版的 Baby Step Gaint Step 即可解决，这部分算出的答案加上 $t$ 就是原同余方程的解。
若 $G_{t} ∤ B$ ，由于 $A^{x} \mod C = (G_{t} \times D \times A^{x - t}) \mod (G_{t} \times C^{'}) = K \cdot G_{t}$ ，所以无解。

程序实现
¶

ebsgs.cpp

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
typedef long long LL;
unordered_map<LL, int> emp;

int ebsgs(LL A, LL B, LL C) {
  LL D = 1, cnt = 0;
  for (LL G; (G = gcd(A, C)) != 1; cnt += 1) {
    if (B % G) return -1;
    B /= G;
    C /= G;
    D = D * A / G % C;
    if (D == B) return cnt;
  }

  emp.clear();
  int M = ceil(sqrt(1.0 * C));

  LL AA = 1;
  for (int x0 = 0; x0 < M; ++x0) {
    if (!emp.count(AA)) emp[AA] = x0;
    AA = AA * A % C;
  }

  B = B * inv(D, C) % C;
  LL Am = inv(powerMod(A, M, C), C);
  for (int k = 0; k < M; ++k) {
    if (emp.count(B)) return emp[B] + cnt + k * M;
    B = B * Am % C;
  }
  return -1;
}

练习
¶

#	Problem	Category	Solution / Code
1	51Nod/X^A Mod P	BSGS	solution.cpp
2	51Nod/X^A Mod B	扩展BSGS	solution.cpp
3	SPJ/MOD	扩展 BSGS	solution.cpp
4	UVa/Code Feat	中国剩余定理	solution.cpp

小结
¶

拖沓了很久，终于耐下性子整理了一下。
鉴于本人能力有限，有误之处欢迎指正。

离散对数(Baby Step Giant Step)

扩展欧几里得算法¶

问题描述¶

问题简析¶

程序实现¶

问题扩展¶

逆元¶

求解逆元¶

程序实现¶

中国剩余定理¶

问题简析¶

程序实现¶

Baby Step Gaint Step¶

问题简析¶

程序实现¶

Extend Baby Step Gaint Step¶

问题简析¶

程序实现¶

练习¶

小结¶

Related¶

扩展欧几里得算法
¶

问题描述
¶

问题简析
¶

程序实现
¶

问题扩展
¶

逆元
¶

求解逆元
¶

程序实现
¶

中国剩余定理
¶

问题简析
¶

程序实现
¶

Baby Step Gaint Step
¶

问题简析
¶

程序实现
¶

Extend Baby Step Gaint Step
¶

问题简析
¶

程序实现
¶

练习
¶

小结
¶

Related
¶