中国剰余定理(CRT)について解説！例題付き

RSA暗号の高速復号化に用いられたり、平方剰余問題に使われたりする中国剰余定理(Chinese Remainder Theorem)。

今回は、これらの問題を解くための準備として中国剰余定理について解説します！

例題も用意しているため、CRTの基本から演習まで行うことができます！

中国剰余定理(CRT)とは？

中国剰余定理は、割り算のあまりに関する連立方程式に使える定理です。

まずはその定理について説明します。

中国剰余定理(CRT)

$n=n_{1}n_{2}, gcd(n_{1}, n_{2})=1$を満たすnについて

$x\equiv x_{1} \bmod n_1, x\equiv x_{2} \bmod n_2$

を満たすような$x$が存在する。その$x$とは

$x \equiv x_{1}n_{2}n_{2}^{-} + x_{2}n_{1}n_{1}^{-} \bmod n$
$n^{-}_{1} \equiv n^{-1}_{1} \bmod n_2, n^{-}_{2} \equiv n^{-1}_{2} \bmod n_1$

である。

nが2つの素因数を持つとき、$\bmod n_{1}$と$\bmod n_{2}$に分けて考えることが可能ということです。

その2つの式を満たすような$x$も2つの素因数から簡単に求めることができます。

中国剰余定理を使って実際に問題を解いてみましょう。

問題

$n=3\times5$であるとき、以下を満たす$x$を求めよ。

$x\equiv 2 \bmod 3, x\equiv 4 \bmod 5$

nが小さいため力技で求められそうですが、中国剰余定理を使います。（ここで用いる文字は、定理を紹介したときと同じものを使用します。）

解法

$n_{2}^{-} \equiv 5^{-1} \equiv 2 \bmod 3$
$n_{1}^{-} \equiv 3^{-1} \equiv 2 \bmod 5$

より、$x$は

$x \equiv 2\times5\times2 + 4\times3\times2 \equiv 14 \bmod 15$

と求まります。

ちなみに、この問題ではnの素因数は2つですが、一般に3つ以上の素因数を持つ場合でもCRTは成立します。この記事では紹介しませんが、調べてみると面白いです。

中国剰余定理を用いることで、RSA暗号における復号を高速化させることができます。

証明は省きますが、以下の式が成立します。

RSAの高速復号

暗号文C、秘密鍵d、$n=n_1n_2$とすると、Cの復号$M\equiv C^d \bmod n$は、

$x\equiv C^d \bmod n_1, x\equiv C^d \bmod n_2$

で求めることができる。

例えば、$C=28, d=7, n=33=3\times11$の平文Mを考えます。

普通に復号する際は、

$M \equiv C^d \equiv 28^7 \bmod 33$

を計算します。しかし、$28^7$を計算することは大変です。高速累乗計算のアルゴリズムを適用させる工夫をしてもよいですが、今回は中国剰余定理を用いた復号を行います。

nの素因数を法とする

$x\equiv 28^7 \bmod 3, x\equiv 28^7 \bmod 11$

を考えます。これは中国剰余定理から成立します。

この$x$の求め方は前述した通りに求めればよいです。そして、この$x$こそが平文Mと等しくなります。

今回は、中国剰余定理（CRT）とその応用について解説しました。

中国剰余定理を用いることでRSA暗号における復号を高速化させることができます。

理解を深めるために、手計算で中国剰余定理を使って求めてみるとよいです。

最後までご覧いただきありがとうございます。お疲れ様でした。