アルゴリズム論特論（塩田）第13回 (2) 中国剰余定理・中国剰余アルゴリズム
前へ / 戻る / 次へ
$\newcommand{\ol}[1]{\overline{#1}}$
$\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$
$\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$
$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$
中国剰余定理
Th.1（中国剰余定理、Chinese Remainder Theorem） $m$ と $n$ を互いに素な 2 つの法とするとき、連立合同式
$\dps{
\left\{
\begin{array}{l}
x \equiv a \pmod{m} \\
x \equiv b \pmod{n} \\
\end{array}
\right.}$
は $\bmod (m\times n)$ で唯一の解 $x$ を持つ。
証明 唯一性 $x$, $y$ が共に解であれば
$\dps{
\left\{
\begin{array}{l}
x \equiv a \equiv y \pmod{m} \\
x \equiv b \equiv y \pmod{n} \\
\end{array}
\right.}$
ですから、$x-y$ は $m$ と $n$ の公倍数であり、$\gcd(m,n)=1$ から
$x \equiv y \pmod{(m\times n)}$
存在 は次のアルゴリズムを実行します。
中国剰余アルゴリズム ( CRA )
Algorithm 2（中国剰余アルゴリズム、Chinese Remainder Algorithm） Th.1 の状況で
- 入力：$a$, $b$, $m$, $n$
- 出力：$x$
- $m$, $n$ を引数として拡張ユークリッドアルゴリズムを実行し
$mu+nv=1$
を満たす $u$, $v$ を求める。
- $x = \{\,a(nv)+b(mu)\,\} \,\%\, (m\times n)$ とおく。
証明 1° より
- $\bmod m$ では $1 = mu+nv \equiv nv$, $\ mu \equiv 0$
- $\bmod n\ $ では $1 = mu+nv \equiv mu$, $nv \equiv 0$
となります。わかり易く表にまとめると
| $nu$ | $mu$ |
| $\bmod m$ | $1$ | $0$ |
| $\bmod n$ | $0$ | $1$ |
従って
- $\bmod m$ では $x \equiv a(nv)+b(mu) \equiv a \times 1 + b \times 0 = a$
- $\bmod n\ $ では $x \equiv a(nv)+b(mu) \equiv a \times 0 + b \times 1 = b$
(証明終)
Ex.3 Alg.2 に従って連立合同式
$\dps{
\left\{
\begin{array}{l}
x \equiv 3 \pmod{\ 7\ } \\
x \equiv 5 \pmod{17} \\
\end{array}
\right.}$
を解いてみましょう。
答え
- $7$, $17$ を引数として拡張ユークリッドアルゴリズムを実行し
$7 \times 5 + 17 \times (-1) = 1$
- $x = \{\,3(17 \times (-2))+5(7 \times 5)\,\} \,\%\, (7\times 17)=73$
注
Rem.4
- 代数学用語を使って書けば、$m$ と $n$ が互いに素のとき
| $\znz{(m \times n)}$ |
$\longrightarrow$ |
$\znz{m}\ \oplus\ \znz{n}$ |
 |
|
|
| $x$ |
$\longmapsto$ |
$(x \,\%\,m,\,x\,\%\,n)$ |
が環の同型になる、というのが中国剰余定理です。
- $\bmod (m \times n)$ の情報は、
$\bmod m$ の情報と$\bmod n$ の情報の組に分割できる、とも言えます。
- 例えば RSA暗号の復号においては、
$\bmod n$ でべき乗を計算する代わりに、
$\bmod p$ と$\bmod q$ でべき乗を計算しておいて最後に中国剰余アルゴリズムを使って $\bmod n$ へ戻す、
という工夫ができます。
法べき乗計算はビット長の3乗オーダーの計算でしたから、約4倍の高速化が図れます。
（ある意味で分割統治法になっています。）