数论与群论密码学-04-中国剩余定理

中国剩余定理

该定理给出了一个将 \(\mathbb{Z}/m\mathbb{Z}\) 分解成数个较小的部分从而降低运算复杂度的方法。

我们需要用到以下构造:给定两个环 \(R_1, R_2\),其笛卡尔乘积

\[ R_1 \times R_2 := \{(x_1, x_2): x_i \in R_i\} \]

通过按分量逐个相加/相乘形成环。

中国剩余定理,第一版

\(m = m_1m_2\)\(gcd(m_1, m_2) = 1\),那么映射

\[ a \bmod m \mapsto ((a \bmod m_1), (a \bmod m_2)) \]

定义了以下环上的同构:

\[ \psi: \mathbb{Z}/m\mathbb{Z} \xrightarrow{\sim} (\mathbb{Z}/m_1\mathbb{Z}) \times (\mathbb{Z}/m_2\mathbb{Z}) \]

因此 \(\mathbb{Z}/m\mathbb{Z}\) 中的运算等价于 \((\mathbb{Z}/m_1\mathbb{Z}) \times (\mathbb{Z}/m_2\mathbb{Z})\) 中的运算。

对于 “\(\psi\) 是环同构” 的断言有以下两个意义:

  1. \(\psi\) 维持了环上的运算: \[ \psi(a+b) = \psi(a) + \psi(b)\\ \psi(ab) = \psi(a)\psi(b) \]
  2. \(\psi\) 定义了一个双射。

其中,

1)是由定义得到的结论;
2)为了证明 \(\psi\) 定义了一个双射,只需证明其是一个单射,由于 \(\mathbb{Z}/m\mathbb{Z}\)\((\mathbb{Z}/m_1\mathbb{Z}) \times (\mathbb{Z}/m_2\mathbb{Z})\) 都含有 \(m=m_1m_2\) 个元素。因此仅需要证明

\[ \psi(a) = \psi(b) \implies a = b~\text{(在 $\mathbb{Z}/m\mathbb{Z}$ 中)} \]

因为有

\[ \begin{aligned} a = b~\text{(在 $\mathbb{Z}/m\mathbb{Z}$ 中)} &\iff a \equiv b \pmod m\\ &\iff m \mid a-b \end{aligned} \]

\[ \begin{array}{rcl} \psi(a) = \psi(b) &\iff &a \equiv b \pmod{m_1} \\ & &a \equiv b \pmod{m_2} \\ &\iff &m_1 \mid a-b \\ & &m_2 \mid a-b \end{array} \]

于是我们仅需要证明

\[ m_1 \mid a-b, m_2 \mid a-b \implies m \mid a-b \]

而由于我们有 \(gcd(m_1, m_2) = 1\),根据欧氏引理,故上述断言得证。

若我们限制定理 8 中的值域,则

\[\psi^\times : (\mathbb{Z}/m\mathbb{Z})^\times \xrightarrow{\sim} (\mathbb{Z}/m_1\mathbb{Z})^\times \times (\mathbb{Z}/m_2\mathbb{Z})^\times\]

定义了群上的同构,因此两群等势,有

\[ \phi(m) = \phi(m_1)\phi(m_2)~\text{若 $gcd(m_1, m_2) = 1$,其中 $m=m_1m_2$} \]

即证明了定理 6 中的式 (1)。

根据环同构的基本性质,有

  1. \(\psi: R_1 \xrightarrow{\sim} R_2\) 为环同构,则 \(\psi^\times : R_1^\times \xrightarrow{\sim} R_2^\times\) 为群同构。
  2. \((R_1 \times R_2)^\times = R_1^\times \times R_2^\times\)

因此

\[\phi(m) = | (\mathbb{Z}/m\mathbb{Z})^\times | \\ \stackrel{\text{$\psi^\times$ 为双射}}{=} | (\mathbb{Z}/m_1\mathbb{Z})^\times \times (\mathbb{Z}/m_2\mathbb{Z})^\times | = \phi(m_1)\phi(m_2)\]

\(m=m_1 \cdots m_t\)\(gcd(m_i, m_j) = 1,~\text{for all $i \ne j$}\),那么

\[ a \bmod m \mapsto (a \bmod m_1, \cdots, a \bmod m_t) \]

定义了环同构

\[ \psi: \mathbb{Z}/m\mathbb{Z} \xrightarrow{\sim} (\mathbb{Z}/m_1\mathbb{Z})^\times \times \cdots \times (\mathbb{Z}/m_t\mathbb{Z}) \]

以及从其中可导出的群同构

\[ \psi^\times : \mathbb{Z}/m\mathbb{Z} \xrightarrow{\sim} (\mathbb{Z}/m_1\mathbb{Z})^\times \times \cdots \times (\mathbb{Z}/m_t\mathbb{Z})^\times \]

从理 2 可根据定理 8 通过在 \(t\) 上进行归纳由类似从理 1 的方式证明。另外也可直接根据以下更广义的欧氏引理证得。

欧几里得引理

\(m=m_1 \cdots m_t\)\(gcd(m_i, m_j) = 1,~\text{for all $i \ne j$}\),那么

\[ m_1 \cdots m_t \mid x \iff m_i \mid x,~\text{for $1 \le i \le t$} \]

注意,定理 8 虽然在理论上给出了降低 \(\mathbb{Z}/m\mathbb{Z}\) 中运算的复杂度的方向,然而其并未给出计算 \(\psi^{-1}\) 的方法,而这是以下定理所要说明的。

中国剩余定理,第二版

\(m=m_1 \cdots m_t\)\(gcd(m_i, m_j) = 1,~\text{for all $i \ne j$}\)(两两互质),那么设

\[ m_i' = \frac{m}{m_i}~\text{或者说 $m_i'=\prod_{j \ne i} m_j$} e_i = m_i'm_i^\star \]

其中 \(m_i^\star \in \mathbb{Z}\) 满足

\[ m_i^\star m_i' \equiv 1 \pmod{m_i} \]

注意,由于两两互质的条件,上述 \(m_i^\star\) 必然存在。

那么,若 \(x, a_1, \cdots, a_t \in \mathbb{Z}\),则有

\[ \begin{array}{cccl} &x &\equiv &a_1 \pmod{m_1}\\ & &\vdots & \\ &x &\equiv &a_1 \pmod{m_1}\\ \iff & x &\equiv & a_1e_1 + \cdots + a_te_t \pmod{\underbrace{m_1 \cdots m_t}_{m}} \end{array} \]

特别地,若 \(\psi(x) = (a_1, a_2)\),则 \(\psi^{-1}(a_1,a_2) \equiv e_1a_1+e_2a_2 \pmod m\)

这样一来,我们可以将在 \(\mathbb{Z}/m\mathbb{Z}\) 中进行四则运算的复杂度由 \(\Theta(log^2(m))\) 降至 \(\Theta(log(m_1)log(m_2))\)。该复杂度主要来源于解 \((\mathbb{Z}/m_1\mathbb{Z})^\times \times (\mathbb{Z}/m_2\mathbb{Z})^\times\) 中的线性同余方程。