算術と数論

中国剰余定理

互いに素な法を持つ合同式の連立は、その積を法として一意な解を持つ。

直観 $7$ を超えて数えずに兵士を数える

ある将軍が兵士を $3$ 人ずつの列に並べると $2$ 人余り、 $5$ 人ずつの列では $3$ 人余り、 $7$ 人ずつの列では $2$ 人余った。兵士は何人いるか?将軍は一度も $7$ を超えて数えていないにもかかわらず、その3つの小さな余り $(2,3,2)$ だけで、 $3\times5\times7=105$ を法として正確な人数が決まってしまう:答えは $23$ (に $105$ の任意の倍数を足したもの)である。これが中国剰余定理(CRT)である:法が互いに素である限り、各 $m_i$ を法とする余りを知ることは、それらの積 $m_1 m_2\cdots m_k$ を法とする余りを知ることとまったく同じ情報を持つ。これにより、巨大な数を法とする1つの難しい計算を、その因数ごとの複数の簡単で独立した計算へと分割し、後から結果を再構成できる。

法

m = 15 = 3 \times 5

の剰余:各剰余

x \bmod 15

は剰余の組

(x \bmod 3,\ x \bmod 5)

によって一意に定まる。

中高主張と明示的な公式

定義: 連立合同式

対ごとに互いに素な法 $m_1,\dots,m_k$ ——すなわち $\gcd(m_i,m_j)=1\quad(i\neq j)$ ——と任意の整数 $a_1,\dots,a_k$ が与えられたとき、連立系 $x \equiv a_i \pmod{m_i}\quad(1\le i\le k)$ はすべての $i$ について同時に法 $m_i$ で $a_i$ と合同になる整数 $x$ を求める。 $M = m_1 m_2 \cdots m_k,\quad M_i = M/m_i$ とおき、 $y_i$ を法 $m_i$ における $M_i$ の逆元とすると( $\gcd(M_i,m_i)=1$ なので存在し、 $M_i y_i \equiv 1 \pmod{m_i}$ を満たす)、解は明示的に $x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$ で与えられる。

x \equiv a_i \pmod{m_i}\quad(1\le i\le k),\qquad \gcd(m_i,m_j)=1\ (i\neq j)

和の各項 $a_i M_i y_i$ は $\equiv a_i \pmod{m_i}$ (なぜなら $M_i y_i\equiv1\pmod{m_i}$ )となり、 $j\neq i$ なるすべてについて $\equiv 0 \pmod{m_j}$ (なぜなら $m_j$ は $M_i = M/m_i$ の因数)となるように作られている。したがって和全体を固定した $m_i$ で簡約すると、 $i$ 番目の項以外はすべて消え、要求通り $a_i$ だけが残る。

x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M},\qquad M = m_1\cdots m_k,\ M_i = M/m_i,\ M_i y_i \equiv 1 \pmod{m_i}

2つの法対 $k$ 個の法
場合	仮定	一意となる法
$2$ つの法 $m_1,m_2$	$\gcd(m_1,m_2)=1$	$m_1 m_2$
$k$ 個の法 $m_1,\dots,m_k$	$i\neq j$ で $\gcd(m_i,m_j)=1$	$M=m_1\cdots m_k$

大学定理

定理: 中国剰余定理(存在と一意性)

$m_1,\dots,m_k$ が対ごとに互いに素( $\gcd(m_i,m_j)=1\quad(i\neq j)$ )ならば、任意の整数 $a_1,\dots,a_k$ に対して連立系 $x \equiv a_i \pmod{m_i}\quad(1\le i\le k)$ は解 $x$ を持ち、任意の2つの解は $M=m_1\cdots m_k$ を法として合同である。

なぜ正しいのか?

法が共通の素因数を持たないため、法 $m_1$ で $a_1$ 余るという条件と法 $m_2$ で $a_2$ 余るという条件は完全に独立した制約である——点の $x$ 座標と $y$ 座標を別々に指定するようなものである。ベズーの等式は、ある1つの法で $1$ になり他のすべての法で $0$ になる「基底ベクトル」を与えてくれるため、解を線形結合として直接構成できる。

証明

まず2つの法の場合( $k=2$ )を証明し、帰納法で拡張する。 $\gcd(m_1,m_2)=1$ より、ベズーの等式から $m_1 u + m_2 v = 1$ を満たす整数 $u,v$ が得られる。 $x_0 = a_1 m_2 v + a_2 m_1 u$ とおく。

法 $m_1$ で確認する: $m_1 u + m_2 v = 1$ より $m_2 v = 1 - m_1 u \equiv 1 \pmod{m_1}$ であり、一方 $m_1 u \equiv 0 \pmod{m_1}$ なので、 $x_0 \equiv a_1\cdot 1 + a_2\cdot 0 = a_1 \pmod{m_1}$ 。

対称的に、法 $m_2$ では: $m_1 u = 1-m_2 v \equiv 1 \pmod{m_2}$ かつ $m_2 v \equiv 0 \pmod{m_2}$ なので、 $x_0 \equiv a_1\cdot 0 + a_2\cdot 1 = a_2 \pmod{m_2}$ 。これで $k=2$ での存在が証明された。

$k=2$ での一意性: $x$ と $x'$ がともに連立系を解くなら、 $x-x'\equiv0\pmod{m_1}$ かつ $x-x'\equiv0\pmod{m_2}$ 、すなわち $m_1$ と $m_2$ はともに $d=x-x'$ を割り切る。ベズーの式 $m_1 u+m_2 v=1$ に $d$ を掛けると: $d = d m_1 u + d m_2 v$ 。 $m_2\mid d$ なので第1項 $d m_1 u$ は $m_1 m_2$ の倍数であり、 $m_1\mid d$ なので第2項 $d m_2 v$ も $m_1 m_2$ の倍数である。よって $m_1 m_2 \mid d$ 、すなわち $x\equiv x'\pmod{m_1 m_2}$ である。

一般の $k>2$ については帰納法による:最初の2つの合同式は( $k=2$ の場合により) $m_1 m_2$ を法とする単一の合同式と同値である; $m_3$ は $m_1$ とも $m_2$ とも互いに素なのでその積 $m_1 m_2$ とも互いに素であり、再び結合でき、以下 $k$ まで同様である。明示的な和 $x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$ もまったく同じ理由で任意の $k$ に対して直接機能することに注意せよ: $M_i = M/m_i$ は $m_i$ と互いに素なので逆元 $y_i$ が存在し、 $j\neq i$ なるすべての項は $M_j$ の因数として $m_i$ を含む。 $\blacksquare$

定理: 環同型としてのCRTと

\varphi

の乗法性

$\gcd(m_1,m_2)=1$ のとき、写像 $\psi(x \bmod m_1 m_2) = (x\bmod m_1,\ x\bmod m_2)$ は環同型 $\mathbb{Z}/(m_1 m_2)\mathbb{Z} \cong (\mathbb{Z}/m_1\mathbb{Z})\times(\mathbb{Z}/m_2\mathbb{Z})$ であり、 $\psi$ を可逆元に制限することで $\varphi(m_1 m_2) = \varphi(m_1)\,\varphi(m_2)$ が証明される。

なぜ正しいのか?

これがCRTの構造的な意味である: $m_1 m_2$ を法とする算術とは、文字通り2つの独立した合同算術(1つは法 $m_1$ 、もう1つは法 $m_2$ )が並走していることそのものなのである。これこそオイラーのトーシェント $\varphi$ が互いに素な数についてきれいに因数分解できる理由であり、またコンピュータが各小さな成分ごとに別々に計算することで巨大整数や暗号の計算を高速化できる理由でもある。

証明

第一に、 $\psi$ はwell-definedである: $x\equiv x'\pmod{m_1 m_2}$ ならば $m_1 m_2\mid(x-x')$ なので、 $m_1$ も $m_2$ も $x-x'$ を割り切り、 $x\equiv x'\pmod{m_1}$ かつ $x\equiv x'\pmod{m_2}$ となる。

第二に、法 $m_i$ での簡約が加法と乗法を保つので(最初の合同式のトピックで証明済み)、 $\psi$ は各座標で加法と乗法を保ち、したがって $\psi$ は環準同型である。

第三に、上の定理1はまさに、任意の組 $(a_1,a_2)$ に対してそこへ写る $x$ が存在し( $\psi$ は全射)、その $x$ が法 $m_1 m_2$ で一意である( $\psi$ は単射)ことを述べている。よって $\psi$ は全単射であり、したがって環同型である。

最後に、直積環 $R_1\times R_2$ において、元 $(u_1,u_2)$ が乗法逆元 $(v_1,v_2)$ を持つのは、 $R_1$ で $u_1 v_1=1$ かつ $R_2$ で $u_2 v_2=1$ となるとき、すなわち両方の座標が可逆であるとき、かつそのときに限る。環同型は可逆性を保つので、 $\mathbb{Z}/(m_1 m_2)\mathbb{Z}$ の可逆元( $\varphi(m_1 m_2)$ 個ある)は、 $(\mathbb{Z}/m_1\mathbb{Z})\times(\mathbb{Z}/m_2\mathbb{Z})$ における可逆元の組( $\varphi(m_1)\,\varphi(m_2)$ 個ある)と一対一に対応する。両辺を数えることで $\varphi(m_1 m_2)=\varphi(m_1)\,\varphi(m_2)$ が得られる。素数べきに対する $\varphi(p^r)=p^r-p^{r-1}$ (互いに素でない数は $p$ の $p^{r-1}$ 個の倍数だけ)と組み合わせれば、前のトピックで使った $\varphi(n)$ の一般の積公式が直ちに導かれる。 $\blacksquare$

発展実世界での応用と具体例

古典的なパズルにとどまらず、中国剰余定理は現代の計算の主力である。すべての実用RSA実装(OpenSSL、BoringSSL、ハードウェアセキュリティモジュール)はCRT-RSA(Quisquater–Couvreur、1982年)を用い、法 $p$ と法 $q$ で別々に計算してからCRTで再結合することで $c^d \bmod pq$ を計算する——法でのべき乗計算には $O((\log m)^3)$ かかり、法のビット長を半分にすると1回のべき乗あたりの計算量が $2^3=8$ 分の1になるため(2回行うので全体では $8/2=4$ 倍高速)、およそ $4$ 倍の高速化になる。同じアイデアが高速な多倍長整数ライブラリや準同型暗号における剰余数系(RNS)、さらには天文や暦の周期計算の基盤となっている。

例: 孫子の元の兵士パズルを解く

$x\equiv2\pmod3$ 、 $x\equiv3\pmod5$ 、 $x\equiv2\pmod7$ を満たす整数 $x$ をすべて求めよ。

解答

法 $m_1=3,m_2=5,m_3=7$ は対ごとに互いに素で、積は $M = 3\times5\times7 = 105$ なので、明示的なCRTの公式が $M_1 = 105/3 = 35$ 、 $M_2 = 105/5 = 21$ 、 $M_3 = 105/7 = 15$ として適用できる。

法 $m_i$ における $M_i$ の各逆元 $y_i$ を求める:(1) $35 \equiv 2 \pmod 3$ であり $2\times2=4\equiv1\pmod3$ なので $y_1=2$ ;(2) $21 \equiv 1 \pmod 5$ なので $y_2=1$ ;(3) $15 \equiv 1 \pmod 7$ なので $y_3=1$ 。

$(a_1,a_2,a_3)=(2,3,2)$ として $x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$ に代入する: $x \equiv 2\cdot35\cdot2 + 3\cdot21\cdot1 + 2\cdot15\cdot1 = 140 + 63 + 30 = 233 \pmod{105}$ 。

$233 = 2\times105 + 23$ なので、法 $105$ で簡約すると $x \equiv 23 \pmod{105}$ となる。検算: $23 = 3\times7+2\equiv2\pmod3$ 、 $23=5\times4+3\equiv3\pmod5$ 、 $23=7\times3+2\equiv2\pmod7$ 。3つすべてが成り立ち、最小の正の解は** $23$ **である。

例: CRTによる高速RSA復号(CRT-RSA)

前のトピックのRSAの例( $p=5,q=11,n=55,d=27$ 、暗号文 $c=8$ )において、法 $55$ で計算する代わりに法 $5$ と法 $11$ での2つの小さな計算に分割することで $m = 8^{27} \bmod 55$ を計算せよ。

解答

法 $p=5$ では:底を $8\equiv3\pmod5$ と簡約し、フェルマーの小定理を使って指数 $d=27$ を $p-1=4$ を法として簡約する( $27 = 4\times6+3$ なので $d_p = 3$ )。すると $m_p = 3^3 = 27 \equiv 2 \pmod 5$ ——たった1回の小さな三乗計算である!

法 $q=11$ では:底は $8$ であり、フェルマーを使って指数 $27$ を $q-1=10$ を法として簡約する( $27 = 10\times2+7$ なので $d_q = 7$ )。 $8^7 \bmod 11$ を計算する: $8\equiv-3\pmod{11}$ なので、 $8^2\equiv9\equiv-2$ 、 $8^4\equiv4$ 、 $8^7 = 8^4\cdot8^2\cdot8\equiv 4\cdot(-2)\cdot(-3)=24\equiv2\pmod{11}$ 。

ここで $m\equiv2\pmod5$ と $m\equiv2\pmod{11}$ をCRTで再結合する:たまたま両方の余りが $2$ なので、法 $55$ での一意な解は直ちに $m\equiv2\pmod{55}$ である(一般には $m_p,m_q$ が異なる場合、2つの法のCRT公式を1回適用する)。 $11$ より大きい数を一度も二乗せず、 $7$ より大きい指数を一度も使わなかったことに注目してほしい—— $2048$ ビットのRSA素数では、同じ分割によって復号時間が約4分の1に短縮される。

よくある誤り. 対ごとに互いに素という条件は任意ではない:もし

\gcd(m_1,m_2)=g>1

ならば、連立系

x\equiv a_1\pmod{m_1},\ x\equiv a_2\pmod{m_2}

が解を持つのは

a_1\equiv a_2\pmod g

のとき、かつそのときに限り、解が存在するときは

m_1 m_2

ではなく

\operatorname{lcm}(m_1,m_2)

を法として一意である。例えば

x\equiv1\pmod4

と

x\equiv0\pmod6

には解がまったくない:第1式は

x

が奇数であることを強い、第2式は

x

が偶数であることを強いるが、これは

a_1=1\not\equiv0=a_2\pmod{\gcd(4,6)}

だからである。明示公式

x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}

でよくある2つ目のミスは、

y_i

を法

m_i

ではなく法

M

での

M_i

の逆元(存在しない!)として計算してしまうことである。

歴史的ノート

この問題の知られる最古の出現は『孫子算経』(紀元3〜5世紀頃、劉徽による263年の『九章算術』注釈とほぼ同じ中国初期数学の時代)第3巻第26問であり、上の例1のmod $3,5,7$ の問題を提示し解いている。インドではアーリヤバタ(499年)とブラフマグプタ(7世紀)が2つの合同式に対する一般的な方法(クッタカ、「粉砕機」)を発展させ、秦九韶は1247年の著書『数書九章』で任意の法に対する完全な一般アルゴリズム(大衍求一術)を発表した;その後レオンハルト・オイラーとカール・フリードリヒ・ガウスがヨーロッパの数学においてこの定理に現代的な代数的定式化を与えた。

劉徽ブラーマグプタレオンハルト・オイラーカール・フリードリヒ・ガウス

研究研究の最前線におけるCRT:高速算術・フォールト攻撃・格子暗号

研究の最前線 2026年時点

研究の現在地(2026年時点)。

1. 高速な整数・多項式乗算。 2021年、David HarveyとJoris van der Hoevenは、 $n$ ビットの2つの整数が $O(n\log n)$ ビット演算で乗算できるという長年予想されていた上界を証明した。多法CRT/RNS技法——巨大な整数や多項式係数を機械語サイズの互いに素な複数の法に分割し、各成分で高速変換により乗算してからCRTで再構成する手法——は、実用的な計算機代数システム(FLINT、GMP、NTL)の中核的な構成要素であり続け、現代のSIMDやGPUアーキテクチャ向けに最適化が進められている。

2. CRT-RSAに対するBellcoreフォールト攻撃とその対策。 CRT-RSA(Quisquater–Couvreur、1982年)は復号を $4$ 倍高速化するが、Boneh、DeMillo、Lipton(1997年)は壊滅的なサイドチャネルの弱点を発見した:もし1回のハードウェア故障で $m_q$ は無傷のまま $m_p$ だけが破損すると、攻撃者は $\tilde s^e \equiv m \pmod q$ だが $\tilde s^e \not\equiv m \pmod p$ となる誤った署名 $\tilde s$ を受け取り、たった1回の最大公約数計算 $\gcd(\tilde s^e - m, n) = q$ でRSAの法が即座に素因数分解されてしまう!CRTベースの実装に対する低オーバーヘッドなフォールト攻撃対策(およびCRT様の数論変換を用いるポスト量子方式に対する同様の故障保護)の設計は、暗号ハードウェア研究における活発なトピックであり続けている。

3. 格子暗号と準同型暗号におけるCRT。 環ベースのポスト量子方式や完全準同型方式では、 $q\equiv1\pmod{2N}$ のとき多項式環 $\mathbb{Z}_q[x]/(x^N+1)$ が多項式版CRTによって $N$ 個の独立したスロットへと分解される——これこそ準同型暗号におけるSIMDバッチ処理の仕組みそのものであり、何千もの平文を1つの暗号文に詰め込んで並列に演算することを可能にしている。

$x\equiv1\pmod3$ かつ $x\equiv2\pmod5$ を満たす最小の非負整数 $x$ を求めよ。

$m_1=4,m_2=9,m_3=25$ のとき、これらを法とするCRT連立系の解は次のどの法に関して一意か:

連立系 $x\equiv1\pmod4$ かつ $x\equiv0\pmod6$ について何が言えるか?

なぜCRTはRSA復号 $c^d\bmod pq$ をおよそ $4$ 倍高速化するのか?

参考文献

Jean-Jacques Quisquater, Christophe Couvreur (1982). Fast decipherment algorithm for RSA public-key cryptosystem · DOI:10.1049/el:19820617
David Harvey, Joris van der Hoeven (2021). Integer multiplication in time O(n log n) · DOI:10.4007/annals.2021.193.2.4