数学 - 中国人剰余定理

中国人剰余定理とは、初等整数論の定理の一つであり、非常に多くの応用が存在する定理である。この記事では、この定理に注目してその一般化と応用について解説する。


連立合同方程式

補題

連立合同方程式

$$ \begin{align} x &\equiv a \mod n_1\\ x &\equiv b \mod n_2 \end{align} $$

の解$x$が一意的に存在することを示す。ここでは、$\gcd(n_1, n_2) = 1$とする。このとき、$un_1 + vn_2 = 1$を満たす$u, v$を拡張ユークリッドの互除法で求めることが可能である。これにより$un_1 = 1 - vn_2$と書けるが、これは$un_1 \equiv 1 \mod n_2$と同値である。同様に、$vn_2 \equiv 1 \mod n_1$である。$avn_2 \equiv a \mod n_1$なので、$avn_2 \equiv x \mod n_1$。同様に、$bun_1 \equiv b \mod n_2$、$bun_1 \equiv x \mod n_2$。

$avn_2 + bun_1$を考える。この式は、$avn_2 + bun_1 \equiv avn_2 \equiv a \equiv x \mod n_1$、$avn_2 + bun_1 \equiv bun_1 \equiv b \equiv x \mod n_2$となる。

$avn_2 + bun_1 \equiv x \mod n_1$、$avn_2 + bun_1 \equiv x \mod n_2$ということは、$avn_2 + bun_1$は$n_1, n_2$の公倍数であると考えられる。$n_1, n_2$の公倍数は最小公倍数$\mathrm{lcm}(n_1, n_2)$の倍数で表せるが、この場合$n_1, n_2$は互いに素であるため、$\mathrm{lcm}(n_1, n_2) = n_1n_2$である。 すると、$avn_2 + bun_1 \equiv x \mod n_1n_2$と書ける。よって、式$avn_2 + bun_1 \mod n_1n_2$は上の連立剰余方程式を満たす。

解が一意的であることを示す。 解$x, y$が存在したとして、$x-y \equiv 0 \mod n_1$, $x-y \equiv 0 \mod n_2$が成り立つ。上と同様の議論により、$x-y \equiv 0 \mod n_1n_2$が成り立つ。つまり、$x, y$は$n_1n_2$を法として合同である。このため、$x, y$は一意的に定まる。

これは、補助定理と呼ばれる定理で、これを一般化することで中国人剰余定理が得られる。

中国人剰余定理 (Chinese Reminder Theorem)

$\gcd(n_i, n_j) = 1$ ($i \neq j$)となるような$n_1, n_2, \ldots, n_k$を法とした連立剰余方程式

$$ \begin{align} x &\equiv a_1 \mod n_1\\ \vdots\\ x & \equiv a_k \mod n_k \end{align} $$

の解$x$は$0 \leq x < \prod ^ k_{i=1} n_i$の範囲に一意的に存在する。

Gaussによる証明がわかりやすい。簡略化した証明を示す。

$\displaystyle M = \prod _ {i = 1} ^ k n_i$, $\displaystyle M _ i = \frac{M}{n_i}$とする。すると、$\gcd(M_i, n_i) = 1$なので、補助定理より$M_iu_i \equiv 1 \mod n_i$となるような$u_i$を探すことができる。後は補助定理と同様の議論により、$\displaystyle x \equiv \sum ^ k _ {i=1} a_iu_iM_i \mod n_i$を計算することで、解$x$を求められる。一意性については補助定理とほぼ同じなので省略する。

法についての一般化

上に示した形では、$n_1, \ldots, n_k$はどの2つをとっても互いに素という条件があった。この条件は実は外すことができる。 ここでは$k=2$の時に限定するが, 実際には任意の$k$について同様のことが言える。(暇があればどうぞ)

法$n_1, \ldots, n_k$について、連立剰余方程式

$$ \begin{align} x &\equiv a_1 \mod n_1\\ x &\equiv a_2 \mod n_2\\ \end{align} $$

を考える。この時、$g = \gcd(n_1, n_2)$とし、$g \neq 1$とする。 拡張ユークリッドの互除法より、$Xn_1 + Yn_2 = g$となるような$X$, $Y$を見つけることが出来る。ここで、$n_1$, $n_2$はそれぞれ$g$で割り切れるため、$n_1' = n_1/g$, $n_2' = n_2/g$と定義すると$Xn_1' + Yn_2' = 1$となる. ここから、$a_1 Y n_2' + a_2 X n_1$を考えることにより補題と同様の議論によって解$x$が計算できる。また、解$x$は$0 \leq x < \mathrm{lcm}(n_1, n_2)$の範囲内に存在する。これは途中の操作から明らか。

実装例:

gist901d223135965308a5f9ff0cf99dd7c8

以上から、$x \equiv a_k \mod n_k$の形の剰余連立方程式は常に解を持つことがわかる。

抽象化

この定理は任意の環上のイデアルへと抽象化できるため、環論での応用が可能だ。本筋ではないため証明については参考文献を見られたい。

$A$を環、$I_1, \cdots, I_n \subsetneq A$をイデアルで、$i \neq j$なら$I_i + I_j = A$であるとする。 このとき、以下の事実が成り立つ。

  • $i = 1, \ldots, n$について、$I_i + \prod_{j \neq i} I_j = A$
  • $I_1 \cap\cdots\cap I_n = I_1\cdots I_n$
  • $A/(I_1\cap\cdots\cap I_n) \simeq A/I_1\times\cdots\times A/I_n$

その系として、以下を得られる。これは非常に便利な事実なので、頭の片隅にでも入れておくと役に立つ(かもしれない)

$m_1,\ldots,m_k \in\mathbb{Z}\backslash\left\{0\right\}$ かつ$i\neq j$なら$\gcd(m_i, m_j) = 1$とする。このとき、 $$ \mathbb{Z}/m_1\cdots m_k\mathbb{Z} \simeq \mathbb{Z}/m_1\mathbb{Z}\times\cdots\times\mathbb{Z}/m_k\mathbb{Z} $$

応用例

このように非常に応用に富む中国人剰余定理だが、実際の応用としてはどのようなものがあるか、暗号の視点から見てみる。

RSA-CRT

RSA暗号はEulerの定理を応用した公開鍵暗号だが、実際の速度的な問題が存在する。というのも、パラメータ$e$は 65537 = 0x10001 = 0b10000000000000001 というように非常に計算しやすいものを比較的自由に選ぶことが出来るが、秘密鍵$d$については殆どの場合$e$から計算されるためにそのような計算しやすさは考慮されない。($d$を任意に選択して$e$を計算すれば良いではないか、ともなるが、そのようにすると多くの場合Boneh-Durfee AttackやCommon Private Exponent Attackのような攻撃の脅威に晒されやすくなってしまう。)つまり、復号時の計算量は非常に多くなってしまうのだ。 ここで、RSA暗号は$\mathbb{Z}/n\mathbb{Z}$つまり$\mathbb{Z}/pq\mathbb{Z}$の上で計算されることを考える。これは、先の系より$\mathbb{Z}/pq\mathbb{Z} \simeq \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z}$と書くことができる。これは、大きな群での計算($\mathbb{Z}/n\mathbb{Z}$)をより小さな群($\mathbb{Z}/p\mathbb{Z}$, $\mathbb{Z}/q\mathbb{Z}$)の上での計算に帰着させられることを示している。 この場合の計算は次のようにされる。

  • $d_p \equiv d \mod p-1$, $d_q \equiv d \mod q-1$を計算しておく。
  • 暗号文$c$について、$m_1 \equiv c^{d_p} \mod p$, $m_2 \equiv c^{d_q} \mod q$を計算する。すると、$m \equiv m_1 \mod p$, $m \equiv m_2 \mod q$という連立方程式が立てられるので、これを中国人剰余定理によって解いて$ m $を求める。

なお、openssl等では中国人剰余定理の内部計算を最適化し、$q^{-1} \mod p$を追加のパラメータとして秘密鍵に加えてある場合がある。

Multi-Prime RSA

RSAは何も$p, q$の2つの素数でないといけないわけではない。多変数に拡張されたRSA暗号を、Multi-Prime RSAと呼ぶ。 Multi-Prime RSAが通常のRSAと異なる点は、どのように$\phi(n)$を計算するかと復号処理だろう。前者についてはEulerのTotient関数について見てもらうとして、今回は復号部分について注目したい。 といっても複雑なことはしない。先の系より剰余類を小さな剰余類の直積と見ることによってRSA-CRTの要領で平文を計算し、中国人剰余定理によって平文を復元するだけだ。

Pohlig-Hellman Attack

Pohlig-Hellman Attackとは、任意の合成数位数の巡回群での離散対数問題を効率よく解くアルゴリズムである。アルゴリズムは以下のように与えられる。

  1. 巡回群$P$とその位数$n = \#P$、位数$n$の素因数分解$n = p_1\cdots p_k$が判明しており、$\gamma = g ^ x $となる$g$, $\gamma$が判明しているとする。
  2. 各$p_i$について、$\beta_i = g^{\phi(n)/p_i}$, $\Gamma_i = \gamma^{\phi(n)/p_i}$を考える。この時、$\beta_i$, $\Gamma_i$は位数$p_i$を持つことに注意する。
  3. $\Gamma_i \equiv \beta_i^{x_i} \mod p_i$なる$x_i$を求める。これはBaby-Step Giant-Step法等適当なアルゴリズムで良い。
  4. 各$x_i$について、$x \equiv x_i \mod p_i$が成り立っている。このため、中国人剰余定理を用いて$x$を求めることが出来る。

今回は乗法巡回群として話を進めたが、これは任意の巡回群に適用可能である。例えば、有限体や楕円曲線の群でも適用できる。

参考文献/参考サイト