数论与群论密码学-02-最大公约数与欧几里得算法

整除性

给定 \(a, b \in \mathbb{Z}\),定义

\[ a \mid b \iff b = ak~\text{for some $k\in\mathbb{Z}$} \]

根据上一章给出的除法算法,该条件等价于 \(rem(b, a) = 0\),因此可于多项式时间内判定。

最大公约数

给定 \(a, b \in \mathbb{Z}\),称使得 \(d \mid a\)\(d \mid b\) 最大的数 \(d\)\(a\)\(b\) 的最大公约数,记为 \(gcd(a, b) := d\)。有时也写作 \((a, b)\).

欧几里得算法

该节给出求 \(a, b \in \mathbb{Z}\) 的最大公约数 \(gcd(a, b)\) 的算法。该算法称作欧几里得算法,别称辗转相除法。后文简称欧氏算法。

\(r_{-1} = a,~ r_0 = b\)
逐次求
\(\qquad r_{i+1} = rem(r_{i-1}, r_i)\)
直到 \(r_{k+1} = 0\)
这时 \(r_k = gcd(a, b)\)

\(\text{计算除法的次数} = k \le 2 \lfloor log_2(m) \rfloor\)

若不失一般性地假设 \(m > n\),则欧氏算法的时间复杂度为 \(\Theta(log^2(m))\)

欧氏算法给出了如下的方程组:
1. \(\lvert n \rvert > r_1 > r_2 > \cdots > r_{k - 1} > r_k > 0\)
2. \(gcd(r_{i - 2}, r_{i - 1}) = gcd(r_{i - 1}, r_i)\)

\(r_{i+2} < \frac{1}{2} r_i\), for \(0 \le i \le k-1\).

如果 \(r_{i+1} < \frac{1}{2} r_i\),那么断言是显然的:因为有 \(r_{i+2} < r_{i+1} \le \frac{1}{2} r_i\).

因此假设 \(r_{i+1} > \frac{1}{2} r_i\),或者说 \(2 r_{i+1} > r_i\).

\(r_{i+1} > r_i - r_{i+1} \ge 0\),因为有 \(r_i > r_{i+1}\).

又因为 \(0 \le r_i - r_{i+1}\)\(r_i = 1 \cdot r_{i+1} + (r_i - r_{i+1})\),我们有 \(r_i - r_{i+1} = r_{i+2} < r_i - \frac{1}{2} r_i = \frac{1}{2} r_i\).

依据上述断言,我们有

\[ n = r_0 > 2 r_2 > 4 r_4 > \cdots > 2^{\lfloor\frac{k}{2}\rfloor} r_{2\lfloor\frac{k}{2}\rfloor} \]

因此迭代的次数为

\[ \begin{aligned} k+1 &\le 2 log_2 n + 2\\ &\le 2 log_2 m + 2 \end{aligned} \]

其中

\[ k-1 \le 2\lfloor\frac{k}{2}\rfloor = 2 log_2 2^{\lfloor\frac{k}{2}\rfloor} \le 2 log_2 n \]

因为每一次除法最多需要进行 \(O(log^2 m)\) 次位运算,可得欧氏算法的复杂度为 \(O(log^3 m)\).

如果我们考虑到每次除法运算中的数越来越小的话,可以证明算法的复杂度为 \(\Theta(log^2 m)\).

拓展欧几里得算法

给定整数 \(m\), \(n\), 符合等式 \[ mx + ny = gcd(m, n) \] 的整数 \(x\), \(y\) 存在,并可通过向后代入的方法在 \(\Theta(log^2(m))\) 位操作内求解。(同时可建设性地证明存在不唯一)

对于所有 \(l, 0 \le l \le k-1\),都存在 \(x_l, y_l \in \mathbb{Z}\),使得

\[ r_{l-1}x_l+ r_l y_l = r_k \]

因此存在 \(x, y \in \mathbb{Z}\) 使得

\[ mx + ny = r_k \]

该方法由于需要记录所有逐次的商 \(q_1, \cdots, q_k\), 因此需要大量的空间。

以下给出更好的算法。

\(r_{-1} = m, r_0 = n\), \(r_1, \cdots, r_k\) 为欧氏算法中的逐项余数,那么

\[ \exists x_i, y_i.~mx_i + ny_i = r_i,~\text{for}~i = -1, \cdots, k \tag{1} \]

特别地,有 \(mx_k + ny_k = gcd(m, n)\).

以上关系可以表达为如下向量递归关系:

\[ (x_{i+1}, y_{i+1}, r_{i+1}) = (x_{i-1}, y_{i-1}, r_{i-1}) - q_{q+1} (x_i, y_i, r_i) \]

其中 \(q_{i+1} = quo(r_{i-1}, r_i)\).

\(i = -1\) 时,取 \((x_{-1}, y_{-1}) = (1, 0)\),
\(i = 0\) 时,取 \((x_0, y_0) = (0, 1)\),
则结论是显然的。

对于 \(i \ge 0\),皆有

\[ \begin{equation} mx_{i-1} + ny_{i-1} = r_{i-1} \tag{①} \end{equation} \] \[ \begin{equation} mx_i + ny_i = r_i \tag{②} \end{equation} \]

根据定义,有

\[ r_{i-1} = q_{i+1}r_i + r_{i+1}\\ r_{i+1} = r_{i-1} - q_{i+1}r_i \]

因此 \(① - q_{i+1}②\):

\[ m(\underbrace{x_{i-1} - q_{i+1}x_i}_{x_{i+1}}) + n(\underbrace{y_{i-1} - q_{i+1}y_i}_{y_{i+1}}) = r_{i-1} - q_{i+1}r_i = r_{i+1} \]

满足之前给出的递归关系。

拓展欧几里得算法的矩阵法

因此,满足等式(1) 的整数可用以下矩阵方法求得:

\(A_0 = \begin{pmatrix} 1 & 0 & m\\ 0 & 1 & n \end{pmatrix}\)
依如下递归关系逐次求 \(A_1, \cdots, A_{k+1}\):

\[ A_i = \begin{pmatrix} R_{i_1}\\ R_{i_2} \end{pmatrix} = \begin{pmatrix} x_{i-1} & y_{i-1} & r_{i-1}\\ x_i & y_i & r_i \end{pmatrix}\\ A_{i+1} = \begin{pmatrix} R_{i_2}\\ R_{i_1} - q_{i+1} R_{i_2} \end{pmatrix} \]

直到 \(r_i = 0\)\(r_{k+1} = 0\).

可用拓展欧氏算法求解更一般的 \(mx+ny=c\).

\(mx + ny = c\) 的解

  1. \[ mx + ny = c ~(m, n, c \in \mathbb{Z}) \] 有整数解 \((x, y)\) 当且仅当 \(gcd(m, n) \mid c\).

    我们可以观察到 \(gcd(m, n) \mid m\)\(gcd(m, n) \mid n\),因此 \(gcd(m, n) \mid \underbrace{mx + ny}_{m, n~\text{的线性组合}}\), 因此 \(gcd(m, n) \mid c\).

  2. \(g = gcd(m, c) \mid c\),那么解由下式给出: \[ x = \frac{c}{g} x_0 + \frac{n}{g} t\\ y = \frac{c}{g} y_0 - \frac{m}{g} \] 其中 \(t \in \mathbb{Z}\), \(x_0, y_0\) 满足 \(m x_0 + n y_0 = g\) 且可由拓展欧氏算法解出。

\(gcd(m, n) = 1\), 那么 \(a \mid mn \iff a \mid m \text{且} a \mid n\).