中国剰余定理

中国剰余定理 (CRT)

互いに素な法に関する連立合同式の一意可解性を述べる定理で、環の同型としても定式化される。『ガロア理論の頂を踏む』『耐量子暗号入門』の代数パートで登場し、RSA の高速化など暗号で多用される。

合同式としての主張

互いに素な $p,q$ と $0\le a<p,0\le b<q$ に対し、

$$x\equiv a(\mathrm{mod}p),x\equiv b(\mathrm{mod}q)$$

を満たす $x$ が $0\le x<pq$ の範囲に一意に存在する。$p,q$ が互いに素でないと一意性は崩れる(例: $p=q=2$)。

環の同型

$$\mathbb{Z}/mn\mathbb{Z}\cong (\mathbb{Z}/m\mathbb{Z})\times (\mathbb{Z}/n\mathbb{Z})(\gcd (m,n)=1)$$

写像 $\phi (x+mn\mathbb{Z})=(x+m\mathbb{Z},x+n\mathbb{Z})$ が well-defined・加法準同型であることを確認し、$ma+nb=1$ を用いて全射性を示し、位数一致から全単射(同型)を結論する。

既約剰余類群への拡張

素冪分解 $N=2^3\cdot 3^4\cdot 5^2$ に対し、単元群も直積に分解する:

$$(\mathbb{Z}/N\mathbb{Z}{)}^{\times }\cong (\mathbb{Z}/2^3\mathbb{Z}{)}^{\times }\times (\mathbb{Z}/3^4\mathbb{Z}{)}^{\times }\times (\mathbb{Z}/5^2\mathbb{Z}{)}^{\times }$$

ガロア理論 / 環と加群 / 準同型定理 / 耐量子暗号(SIDH) の基礎。関連: _moc-book-notes