暗号もパズルも解く鍵：中国剰余定理を基礎から応用まで
目次
導入
複数の「割り算の余り」に同時に答える方法を提供するのが中国剰余定理です。例えば「ある数を3で割ると余り2、5で割ると余り3になるとき、その数は何か」といった問題を考えてみましょう。このような同時合同式の問題は一見複雑に見えますが、中国剰余定理を使えばシステム的に解を求めることができます。
中国剰余定理を学ぶ理由は多方面にあります。歴史的には中国の数学者が残した知恵として知られています。実際、中国剰余定理には多くの応用例があります。例えば暗号分野ではRSA暗号の高速処理に利用されますし、コンピュータでは大きな数の計算をより小さな数同士に分割して効率化することができます。さらに、スケジューリングやカレンダー計算など、複数の周期が絡む問題の解決にも役立ちます。
- パズル・ゲーム:同時に複数の余りが与えられるとき、元の数を求めるパズルを解く。
- 暗号通信:RSAなど公開鍵暗号の計算を高速化する。
- コンピュータ工学:大きな数を小さい数の組に分けて計算する「分割と征服」の考え方に応用。
- 周期性の問題:複数の周期を持つ現象（カレンダー、信号、スケジューリング）で同時に条件を満たす時刻を求める。
これらの例からわかるように、中国剰余定理は数学の面白さだけでなく、実世界の問題解決にも有用な定理です。これから、定理の内容や証明、そして具体的な使い方と応用例を詳しく見ていきましょう。
定理の内容と意味
中国剰余定理の主張は次のとおりです。整数 (m_1,m_2,dots,m_k) が互いに素であり、(x equiv a_i pmod{m_i})（(i=1,2,dots,k)）という合同式の連立系を考えます。このとき、すべての合同式を満たす整数 (x) が少なくとも1つ存在し、その解は法 (M = m_1 m_2 dots m_k) において一意になります。言い換えると、与えられた余りの条件から「(x) の値は (M) を法として一つに定まる」ことを意味します。たとえば、解 (x) が求まれば、それに (M) の倍数を加えたすべての数が合同式の解となりますが、法 (M) まで考えれば解はただ一つです。
数学的な背景
中国剰余定理を理解するために、まず基本的な概念を確認しましょう。合同式 (a equiv b pmod{m}) は「(a) と (b) を (m) で割った余りが等しい」ことを表し、すなわち (a – b) が (m) の倍数であることを意味します。たとえば、(17 equiv 5 pmod{6}) という式は、17-5=12が6の倍数であることを言っています。
また、2つの整数 (m_1) と (m_2) が 互いに素であるとは、(gcd(m_1,m_2)=1)（最大公約数が1）であることをいいます。中国剰余定理では、すべての法 (m_i) がお互いに素であることが前提条件となります。もし互いに素でない場合、たとえば (m_1) と (m_2) の最大公約数 (d) が1でないとき、合同式 (x equiv a_1 pmod{m_1}) と (x equiv a_2 pmod{m_2}) の両方を満たす (x) は存在しないことがあります（具体的には (a_1 equiv a_2 pmod{d}) でないと解は存在しません）。
- 合同式:(a equiv b pmod{m}) は「(a) と (b) を (m) で割った余りが同じ」こと。すなわち (m) が (a-b) を割り切る。
- 互いに素:整数 (m_1,m_2) が互いに素とは、(gcd(m_1,m_2)=1) であること。中国剰余定理ではすべての法が互いに素でなければならない。
- 一次合同式の解:式 (a x equiv b pmod{m}) が解を持つのは (gcd(a,m)) が (b) を割り切るときです。特に (gcd(a,m)=1) のときは常に解が存在し、逆元を使って解くことができます。
証明
まず合同式が2つの場合について示します。(m_1)と(m_2)が互いに素であれば、拡張ユークリッド互除法により整数 (s_1, s_2) が見つかり、(m_1 s_1 + m_2 s_2 = 1) が成り立ちます。これを使い、例えば次のように解 (x) を構成します: (x = a_2 m_1 s_1 + a_1 m_2 s_2)。すると (x equiv a_1 pmod{m_1}) かつ (x equiv a_2 pmod{m_2}) が成り立ち、条件を満たす整数 (x) が存在することが示せます。さらに、もし2つの解 (x,y) があれば、両方の合同式を引き算して (x – y equiv 0 pmod{m_1}) かつ (x – y equiv 0 pmod{m_2}) となります。これは (x-y) が (m_1 m_2) の倍数であることを意味し、(bmod m_1 m_2) において (x equiv y) となります。したがって解は法 (m_1m_2) で一意です。
次に一般の場合を考えます。たとえば帰納法で証明する方法があります。まず最初の2つの合同式から解を求め、その解を使って3番目の合同式と連立させます。この手順を繰り返せば、すべての合同式に解が存在することがわかります。さらに、より一般的な構成法としては、(N = m_1 m_2 dots m_k) とおき、各 (i) に対し (N_i = N / m_i) の逆元 (y_i) を計算して次のように (x) を構成する方法があります:
( x = sum_{i=1}^k a_i N_i y_i )
ここで各 (y_i) は (N_i y_i equiv 1 pmod{m_i}) を満たすものです。このように構成した (x) は各合同式を満たし、先と同様に一意性も示せます。以上で中国剰余定理の証明を終わります。
解法の手順
中国剰余定理を用いて合同式の解を求める一般的な手順を以下に示します。
- 全ての法 (m_1,m_2,dots,m_k) の積を計算し、(N = m_1 m_2 dots m_k) とします。
- 各 (i) について (N_i = N / m_i) を計算し、(N_i y_i equiv 1 pmod{m_i}) を満たす逆元 (y_i) を求めます（拡張ユークリッド互除法で計算できます）。
- 以上より、解の一つとして (x = sum_{i=1}^k a_i N_i y_i) を計算し、最後に (x) を (N) で割った余りを取ります。これが求める整数解です。
- 別の手法として、合同式を2つずつ順に組み合わせる方法もあります。まず2つの合同式を解いて得た解をもとに、次の式と連立する手続きを繰り返していく方法です。
以上の手順に従えば、手計算でもプログラムでも中国剰余定理による解法が行えます。
例題
いくつかの例題を解いて、中国剰余定理の使い方を確認しましょう。
例題1
(x equiv 2 pmod{3})、(x equiv 3 pmod{5}) を満たす整数 (x) を求めよ。
- (N = 3 times 5 = 15)。(N_1 = 15/3 = 5)、(N_2 = 15/5 = 3)。
- それぞれの逆元を求める。(5y_1 equiv 1 pmod{3}) なので (y_1 = 2)。(3y_2 equiv 1 pmod{5}) なので (y_2 = 2)。
- 解の一つとして (x = 2 times 5 times 2 + 3 times 3 times 2 = 38)。(x bmod 15 = 38 bmod 15 = 8) となる。
答え: (x equiv 8 pmod{15})（すべての解はこの値に15の倍数を加えたもの）。
例題2
(x equiv 1 pmod{2})、(x equiv 2 pmod{3})、(x equiv 3 pmod{5}) を満たす整数 (x) を求めよ。
- (N = 2 times 3 times 5 = 30)。(N_1 = 30/2 = 15)、(N_2 = 30/3 = 10)、(N_3 = 30/5 = 6)。
- 逆元を求める。(15y_1 equiv 1 pmod{2}) なので (y_1 = 1)。(10y_2 equiv 1 pmod{3}) なので (y_2 = 1)。(6y_3 equiv 1 pmod{5}) なので (y_3 = 1)。
- (x = 1 times 15 times 1 + 2 times 10 times 1 + 3 times 6 times 1 = 53)。(x bmod 30 = 23) となる。
答え: (x equiv 23 pmod{30})（すべての解はこの値に30の倍数を加えたもの）。
例題3
(x equiv 3 pmod{7})、(x equiv 4 pmod{11})、(x equiv 6 pmod{13}) を満たす整数 (x) を求めよ。
- (N = 7 times 11 times 13 = 1001)。(N_1 = 1001/7 = 143)、(N_2 = 1001/11 = 91)、(N_3 = 1001/13 = 77)。
- (143 equiv 3 pmod{7}) なので (3y_1 equiv 1 pmod{7}) となり (y_1 = 5)。(91 equiv 3 pmod{11}) なので (3y_2 equiv 1 pmod{11}) となり (y_2 = 4)。(77 equiv 12 pmod{13}) なので (12y_3 equiv 1 pmod{13}) となり (y_3 = 12)。
- (x = 3 times 143 times 5 + 4 times 91 times 4 + 6 times 77 times 12 = 9145)。(x bmod 1001 = 136) となる。
答え: (x equiv 136 pmod{1001})（すべての解はこの値に1001の倍数を加えたもの）。
例題4
(x equiv 1 pmod{3})、(x equiv 2 pmod{4})、(x equiv 3 pmod{5})、(x equiv 4 pmod{7}) を満たす整数 (x) を求めよ。
- (N = 3 times 4 times 5 times 7 = 420)。(N_1 = 420/3 = 140)、(N_2 = 420/4 = 105)、(N_3 = 420/5 = 84)、(N_4 = 420/7 = 60)。
- (140 equiv 2 pmod{3}) なので (2y_1 equiv 1 pmod{3}) となり (y_1 = 2)。(105 equiv 1 pmod{4}) なので (y_2 = 1)。(84 equiv 4 pmod{5}) なので (4y_3 equiv 1 pmod{5}) となり (y_3 = 4)。(60 equiv 4 pmod{7}) なので (4y_4 equiv 1 pmod{7}) となり (y_4 = 2)。
- (x = 1 times 140 times 2 + 2 times 105 times 1 + 3 times 84 times 4 + 4 times 60 times 2 = 1978)。(x bmod 420 = 1978 bmod 420 = 298) となる。
答え: (x equiv 298 pmod{420})（すべての解はこの値に420の倍数を加えたもの）。
応用例
中国剰余定理は数学的な興味を超えて、様々な分野で応用されています。
- 暗号技術:RSA暗号など公開鍵暗号の計算において、モジュロ演算を効率化するためにCRTが使われています。大きな素数の積に対する演算を複数の小さい素数に分割して計算することで、処理が高速になります。
- 情報通信・符号理論:データ符号化やエラー訂正符号でCRTの考え方が応用されます。また、信号の位相から周期を求めるレーダーやGNSS測位などでは、複数の周波数から真の位相を求める際にCRTが使われることがあります。
- アルゴリズムの高速化:大規模な整数演算や高速フーリエ変換(FFT)の計算で、CRTを使って計算を分割・並列化する方法があります。これにより計算の効率が向上します。
- ゲーム・パズル:複数の条件が与えられる数当てパズルの解法にCRTが使われます。歴史的には、三国時代の暦を題材に「42年、24年、36年を周期とする暦」の問題をCRTで解く例があります。
まとめ
- 中国剰余定理は、互いに素な複数の法に対する合同式の連立を解く方法を示し、解は法の積で一意に定まることを保証します。
- 証明では拡張ユークリッド互除法を使って具体的に解を構成できます。一般の場合も帰納法や逆元を使った公式で存在と一意性を示せます。
- 実際の解法では、法の積 (N) を求め、各 (N_i=N/m_i) に対して逆元を計算して解を構成する手順に従います。
- CRTの考え方は暗号や情報理論、計算機科学で広く使われ、複数条件の問題を簡単にしたり計算を高速化したりする強力なツールとなります。
以上、中国剰余定理の基本から証明、具体的な解法と応用例まで解説しました。これらの内容を理解し、さまざまな問題に取り組んでみてください。
