機械翻訳について
この記事の一部は DeepSeek の支援を受けて翻訳されています。訳文には不正確な箇所が含まれる場合があり、言語や文化の違いにより、一部の特有の用語や文化的背景が理解しにくいことがあります。正確な表現を確認したい場合は原文をお読みください。文化的背景や内容についてご不明な点があれば、サイドバーの連絡先からお気軽にお問い合わせください。ご説明します。
数字当てゲーム
三人行けば七十は稀、五樹の梅花は廿一支、七子団らんはまさに半月、百五を除けば答えは得られる。
———（明）程大位『算法統宗』
私が「中国の剰余定理」に初めて興味を持ったのは、ひとえにその名が数ある定理の中でひときわ異彩を放っていたからだ。その解法である「秦九韶の大衍求一術」もまた、きわめて典雅で、中学生の尽きない想像力を大いにかき立てる神聖な響きを持つ。この神聖なものは南北朝時代の『孫子算経』に由来する。春秋時代に呉に仕えて兵を率いた孫子ではなく、南北朝時代の数学者である孫先生であり、「雉兎同籠（=日本の鶴亀算）」の問題もこの書から出ている。
私たちは現代、学校や仕事が終わると推理パズルや脱出ゲームに夢中になるが、昔の人々は孫先生の算経を一冊買い、毎日畑を耕し終えたり、戦を終えて（生きて帰れれば）家に戻ると、それを開いて、ウサギは何匹か、軍勢は何人かを計算した。現代人が風変わりな口訣で要点を暗記するように、冒頭の詩は、明代の謎解きの達人が孫先生のこの遊びを遊んだ末にまとめた口訣である。今、我々もそれを遊んでみよう。
もしあなたがいま南北朝時代にタイムスリップし、軍官に間者として捕らえられたとしよう。軍官は言う、「陣営に何人の兵がいるか当てられれば、お前は漢人だと証明できるから放免してやる。さもなくば胡人が送り込んだ間者だ」と。しかし、あなたは三つのことしか見られない。
- 衛兵を３列に並べると２人余る。
- ５列に並べると３人余る。
- ７列に並べるとまた２人余る。
あなたならどう推測するか。
多くの人の第一反応はおそらく、「ひとつずつ試す」ことだろう。 13 を試し、違う。17 を試し、違う。19 を試し、違う……と、三つの条件を同時に満たす数に当たるまで試し続ける。
もちろん、それもできる。ただ、それは少々不可能に近い。三回も試せば首が飛ぶだろう。むしろ、これら三つの条件を満たす解がたくさんあるかもしれないではないか。世の中には、３で割って２余る数は無数にあり、５で割って３余る数も無数にある……。
この問題はまさに、人を困らせるためのものだ。しかし、頭の中で演算してみると、条件は一見断片的で解が一つには見えなくとも、最終的にはただ一つの整数に落ち着く。たくさんではなく、ぼんやりした区間でもなく、まるで確固たる一つの数であるかのように。
実際に試してみよう。
１から探し始め、「３で割って２余る」数を挙げると、2、5、8、11、14、17、20、23、26、29、32……
次に、これらのうち「５で割って３余る」ものは、8、23、38……
さらに、その中で「７で割って２余る」ものは、23。
つまり23である。
（作者：Cmglee、ウィキメディア・コモンズ、CC BY-SA 4.0）
この答えには、喜ばしい不確定感が伴う。ようやく見つけた、しかしこの先にもうないとどうして言い切れるのか。
一つずつ試してはいけない
我々は整数を「次々に連なるもの」と捉えすぎている。
1、2、3、4、5……まるで階段のように、一段ずつ上っていく。だから「３で割って２余り、５で割って３余り、７で割って２余る」という条件に遭遇すると、直感も「では頭から調べよう」となる。
しかしこのやり方の問題は明らかだ。階段があまりに長すぎる。
求められているのは、複数の条件を同時に満たす一つの数であって、どれか一つの条件だけではない。条件が増えると、闇雲に試すことは素朴だが骨の折れる仕事になる。とりわけ数字が大きくなると、この仕事はただちに体裁を失う。百個の数を試してみても、正解の隅にも触れられないかもしれない。数を試みるという行為は、そもそも「全探索」の匂いを帯びている。長い一本の線の中から的を探すことを前提としているのだ。
これはよく日付の計算に似ている。
今日が金曜日だとして、１日後は土曜日、２日後は日曜日。100日後は何曜日か。後ろへ、後ろへと100日分押し出して、一日ずつ数える。数え間違えたらもう一度最初から。
余りはすぐそばで悲しそうにあなたを見つめている。
余りは100日後が何曜日かを知る手立てを直接は与えないが、その整数が、ある循環系のどの位置にあるかを教えてくれる。
余りはいかに我々を助けるか
私はモジュロ演算という概念がとても好きだ。ある数を別の数で割り、その余りを取る。そこにはきわめて日常的な気配がある。
先ほどの曜日の問題に戻ろう。
今日は金曜日。７日後はまた金曜日。14日後も金曜日。15日後は１日余るから、一日後ろにずらして土曜日。20日後なら、三七二十一で一日足りないから一日前にずらして木曜日。100日後は、14回の整除で余り２日だから日曜日となる。つまり、曜日という仕組みは本質的に循環している。どれだけ日数が過ぎたかは知らなくてよく、「７で割った余り」だけがわかれば十分なのだ。
時計も同様だ。
いま３時なら、12時間後も３時である。時計は無限に延びる直線ではなく、一つの円だ。時間はその上を歩み、いつか必ず一周して戻ってくる。時間を知りたければ、時計を見る。正常な人間なら誰一人として、まず12を見てから、そこから何時間進んだか数えて今の時刻を判断しようとはしないだろう。針が文字盤のどこを指しているかを一目で捉える。たとえ文字盤に数字が書かれていなくても、そうするはずだ。
カレンダーも同じである。一月は30日、31日、28日、そして閏年まである。時間は前に進んでいると思いきや、実はある種のパターンを伴いながら繰り返し現れているのだ。
数学はこのことを抽象化し、「法（modulus）」と呼ぶ。一つの「法」は一つの循環である。たとえば、「7で割った余りを取る」ことを「法7（$mod$ $7$）」と呼ぶが、これは曜日の世界で話すことにほかならない。「12で割った余りを取る」ことは、時計の世界で話すことだ。一日は24時間だから、翌日の午前１時は我々夜更かし組にとっては今日の25時であり、実際「25時 ≡ 1時 (mod 24)」である。
こうして、数はもはやそれ自身だけではなくなる。異なる法のもとで、異なる側面を現す。
これはまるで人間に似ている。
家庭で、学校で、友人の前で、愛する人の前で、見せる姿はどれも完全に同じではない。一瞬だけでは、その人を正確に見極められない場合がある。しかし、たくさんの側面を見ることができれば、より真実に近づく。
ある整数が法3でどのような姿か、法5でどのような姿か、法7でどのような姿か。こうした「余り」が、その数を固定するのだ。
ここから数論に入る
ガウスは言った。
数学は科学の女王であり、数論は数学の女王である。
数論とはすなわち整数を研究する学問である。
整数の世界は、一見地味で、素朴ですらあるが、その内部の秩序は驚くほど深い。現代数学の多く、現代計算機科学の多く、現代暗号学の多くが、最後には整数へ、余りへ、除法の残影へと立ち返る。まったくもって不思議だ。
モジュロ演算は数論の最も重要な道具の一つである。微積分には導関数が、線形代数には行列が、幾何には座標がある。
そして数論において最もよく使われる道具の一つが「法（モジュロ）」である。異なる数が、モジュロ演算の世界では同じ数と見なされる。まさに25時 ≡ 1時 (mod 24)のように、曜日でいえば「週八」 ≡ 月曜日 (mod 7)となる。この等価関係を**合同（Congruence）**と呼ぶ。
graph TD M["数学"] M --> N["数論"] M --> FF["微積分"] N --> A["整数"] A --> B["整除"] B --> B1["最大公約数（GCD）"] B --> B2["最小公倍数（LCM）"] A --> C["素数"] C --> C1["素因数分解"] B --> D["合同（モジュロ演算）"] D --> E["ユークリッドの互除法"] E --> E1["拡張ユークリッドの互除法"] D --> F["オイラーの定理"] D --> G["フェルマーの小定理"] D --> H["中国の剰余定理"] E1 --> H H --> I["現代暗号"] I --> I1["RSA"] I --> I2["ECC（楕円曲線暗号）"] I --> I3["デジタル署名"] I3 --> I4["ブロックチェーン"]
謎に立ち返り、ついに数式の登場
ここまで長々と述べてきたのは、すべては伏線に過ぎない。つまり、これらのアルファベットや三本線の記号が何を表すかを知ってもらうためであり、ここまで来て数式を書かないのは現代数学に少々申し訳が立たない。
そこで、数式を出現させる。ただし、ゆっくりと。
我々が探している整数を (x) とすると、それは以下を満たす。
$$x \equiv a_1 \pmod{m_1}$$$$x \equiv a_2 \pmod{m_2}$$$$\cdots$$$$x \equiv a_n \pmod{m_n}$$つまり、$x$ は $m_1$ で割ると $a_1$ 余り、$m_2$ で割ると $a_2$ 余り、…… $m_n$ で割ると $a_n$ 余る。
中国の剰余定理が教えるところによれば、これら法 $m_1, m_2, \dots, m_n$ が互いに素であるならば、この連立合同方程式には必ず解が存在し、しかも
$$ M = m_1 m_2 \cdots m_n $$を法とする世界では、その解は一意である。
「互いに素」とは何か
我々が求めるのは、これら法が可能なかぎり独立していることである。なぜなら、特定の数を指し示したいのに、6 と 9 を法に取れば、両者は共通の因数 3 を含み、余りの間に重複が生じてしまう。そんなのは滅茶苦茶だ。
したがって、我々が割る数字は、任意の二つが共通の因数を持ってはならない。たとえば、3 と 5 は互いに素（お互いを構成する因数を持たない）であり、3 と 7 も互いに素、5 と 7 も互いに素である。これらの間には共通の因数がなく、位置を特定する機会を無駄にしない。
だからこそ、中国の剰余定理はあらゆる法に対して無条件に成り立つわけではなく、明確な境界を持つ。数学の最も魅力的な点の一つがここにある。決して軽々しく法螺を吹かない。常に条件をきちんと書き記すのである。
なぜ解は「一意」なのか
注意すべきは、この「一意」とは、永遠にただ一つの整数しか満たさないという意味ではなく、法 (M) の世界において一意だということである。
言い換えれば、同じ一連の余り条件を満たす整数は無数に存在しうるが、それらは互いに (M) の倍数だけ異なっている。法 (M) の世界にとっては、それらは実質的に同じ答え、すなわち合同なのである。
これもまた、私がモジュロ演算を好きな理由の一つだ。「無数の似た対象」を一つの明快なカテゴリーに圧縮してくれる。海面の波紋のように、一つひとつの輪は動いていても、それらが同じリズムに属していることがわかる。
構成の考え方
数学は単に結論を与えるだけでなく、橋を架ける道筋を与える。
$$ M_i = \frac{M}{m_i} $$と置く。これは、総積 (M) を i 番目の法で割って得られる部分である。$M_i$ と $m_i$ は互いに素だから、ある整数 $y_i$ を見つけて、
$$ M_i y_i \equiv 1 \pmod{m_i} $$とできる。この意味するところは、($M_i$) を法 ($m_i$) の世界で 1 に変えたい、それには適当な数 ($y_i$) を掛ければよい、ということである。すると解は次のように書ける。
$$ x \equiv \sum_{i=1}^n a_i M_i y_i \pmod{M} $$論理は実に素朴だ。なぜなら ($M_i$) を法 ($m_j$) の世界に置いたとき、($j=i$) の項以外はすべて ($m_j$) で割り切れて 0 になるからである。対応する項だけが残り、ちょうど ($a_i$) に等しくなる。
これは非常に美しい「指向性」構造である。各項は自分の法に対してのみ語りかけ、他の法に対しては沈黙する。
拡張ユークリッドの互除法とは何か
ここで気づくのは、上記の構成には ($y_i$) を見つけること、すなわち乗法逆元（ある数にその逆元を掛けると 1 になる。$2\times\frac12=1$ なら $\frac12$ は 2 の乗法逆元）を求めることが必要だという点である。どうやって見つけるのか。 そこに登場するのが拡張ユークリッドの互除法である。 簡単に言えば、ユークリッドの互除法は本来、最大公約数を求めるためのものだ。拡張版はさらに、二つの数が互いに素ならば、1 をそれらの整数結合として書けることを教えてくれる。つまり、整数 $u, v$ を見つけて、
$$ au + bv = 1 $$とできる。ひとたび 1 を表せれば、逆元もおのずと現れる。 ユークリッドの互除法はたいへん立派な気質を備えている。地道に除法を繰り返していくうちに、構造が立ち現れてくるのである。
現代の本質：23 を実際に計算する
それでは先ほどの問題を実際に解いてみよう。
$$ x \equiv 2 \pmod{3} $$$$ x \equiv 3 \pmod{5} $$$$ x \equiv 2 \pmod{7} $$法はそれぞれ 3、5、7 であり、二つずつが互いに素であるから、中国の剰余定理が使える。 まず総積を計算する。
$$ M = 3 \times 5 \times 7 = 105 $$次にそれぞれを計算する。
$$ M_1 = \frac{105}{3} = 35,\quad M_2 = \frac{105}{5} = 21,\quad M_3 = \frac{105}{7} = 15 $$次に、各 $M_i$ を対応する法のもとで 1 にする。 $m_1=3$ について $y_1$ を求める。条件は
$$ 35y_1 \equiv 1 \pmod{3} $$35 を 3 で割った余りは 2 だから、実際には
$$ 2y_1 \equiv 1 \pmod{3} $$を解けばよい。試すと、$y_1=2$ のとき $2\times 2=4\equiv 1 \pmod{3}$。よって $y_1=2$。
$m_2=5$ について $y_2$ を求める。
$$ 21y_2 \equiv 1 \pmod{5} $$21 を 5 で割ると余り 1 だから、
$$ y_2 \equiv 1 \pmod{5} $$最も簡単な $y_2=1$ を取る。
$m_3=7$ について $y_3$ を求める。
$$ 15y_3 \equiv 1 \pmod{7} $$15 を 7 で割ると余り 1 だから、
$$ y_3 \equiv 1 \pmod{7} $$最も簡単な $y_3=1$ を取る。
すると公式から
$$ x \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 \pmod{105} $$項ごとに計算する。
$$ 2 \cdot 35 \cdot 2 = 140 $$$$ 3 \cdot 21 = 63 $$$$ 2 \cdot 15 = 30 $$足し合わせると
$ 140+63+30=233 $
さらに 105 で法を取る。
$$ 233 \equiv 23 \pmod{105} $$したがって解は
$$ x \equiv 23 \pmod{105} $$言い換えれば、23、128、233、338……はいずれもこの一連の余り条件を満たすが、法 105 の世界では同一の答えなのである。
flowchart LR A["x ≡ 2 (mod 3)"] B["x ≡ 3 (mod 5)"] C["x ≡ 2 (mod 7)"] A --> D["35 × 逆元 × 2"] B --> E["21 × 逆元 × 3"] C --> F["15 × 逆元 × 2"] D --> G["足し合わせ"] E --> G F --> G G --> H["x = 23"]
古人の方法：冒頭の詩に立ち返る
さて、もう一度冒頭のあの口訣の詩を見てみよう。これは程大位が秦九韶の解法をまとめたものである。
三人行けば七十は稀。
３で割った余りに 70 を掛ける。
なぜなら $70\equiv35=5\times7$ を同時に満たし、かつ $70\equiv1\pmod3$、$70\equiv0\pmod5$、$70\equiv0\pmod7$ だからである。
これは、70 を掛けると、法 3 の世界では元の余りを保ち、法 5 と法 7 の世界では完全に「消える」ことを意味する。
五樹の梅花は廿一支。
「廿一」はすなわち二十一である。
５で割った余りに 21 を掛ける。
なぜなら $21=3\times7$ であり、かつ $21\equiv1\pmod5$、同時に $21\equiv0\pmod3$、$21\equiv0\pmod7$ だからである。だから、この項は法 5 の条件にだけ影響し、他の二つの条件を乱さない。
七子団らんはまさに半月。
古人の言う「半月」とは十五である。
７で割った余りに 15 を掛ける。
なぜなら $15=3\times5$ は $15\equiv1\pmod7$ を満たし、同時に $15\equiv0\pmod3$、$15\equiv0\pmod5$ だからである。
これもまた、自分の受け持つ条件だけを担当する。こうして、きわめて不思議な三つの数字が得られたのである。
| 係数 | 法 3 | 法 5 | 法 7 |
|---|---|---|---|
| 70 | 1 | 0 | 0 |
| 21 | 0 | 1 | 0 |
| 15 | 0 | 0 | 1 |
- 70 は法 3 だけを受け持つ。
- 21 は法 5 だけを受け持つ。
- 15 は法 7 だけを受け持つ。
これらをどのように足し合わせても、互いに影響し合うことはない。
百五を除けば答えは得られる。
ここでの「百五」こそ、$105=3\times5\times7$ である。
最初の三項をすべて足した後、105 を繰り返し引いていく（今日でいう105 で法を取る）。最小の正整数が得られるまで続ければ、それが最終的な答えとなる。
ここまで読んで、もしかすると、これは先ほど紹介した現代の方法とはどこか違うように感じたかもしれない。つい先ほど覚えた公式では、さらに「乗法逆元」を計算する必要があったのに、この口訣にはその記述がないのはなぜか。
その理由は、これがきわめて幸運な特殊例だからである。
法 (3、5、7) に対しては、
$$ 70\equiv1\pmod3, $$$$ 21\equiv1\pmod5, $$$$ 15\equiv1\pmod7. $$三つの係数が、もともとそれぞれの乗法逆元になっているために、追加の計算が一切不要なのである。
一般の中国の剰余定理の問題では、このような幸運はふつう起こらない。たとえば法が (4、9、11) や (5、7、11) になった場合、$M_i=\frac{M}{m_i}$ を使うだけでは条件を満たせず、必ず対応する乗法逆元を掛けなければならない。それが現代の教科書にある汎用公式である。
$$ x\equiv\sum a_iM_iN_i\pmod M, $$ここで ($N_i$) は ($M_i$) の対応する法における乗法逆元である。
言い換えれば、この口訣は、まったく別種のアルゴリズムなのではなく、現代の中国の剰余定理の公式が、法がたまたま 3、5、7 である場合の優美な特殊解法にほかならない。「勾股定理」でいう「勾三、股四、弦五」と同じく、いずれも古の中国の数学者たちが見出した定理の特殊例なのである。
千年前の古人は「乗法逆元」なるものは知らず、ましてや現代の合同式を書き下しもしなかった。しかし彼らは、70、21、15 という三つの不思議な数字をすでに発見し、それらを二十八字の口訣の中に凝縮した。今日、我々が現代代数学の立場で見つめ直しても、それがまさしく中国の剰余定理の中核的思想であることがわかるのである。
インターネットでの応用
HTTPS ウェブサイトを開くとき
たとえば当サイトにアクセスしたとしよう。
あなたのブラウザと私のサーバーとの間でハンドシェイクが行われる。
その中でサーバーは次のことを証明しなければならない。
「私がまさしく hpu.edu.kg である。」
その方法は、次のとおりである。
自分の RSA 秘密鍵 を用いて、あるデータに対してデジタル署名を行う。
ここで問題が生じる。
RSA の秘密鍵演算はきわめて遅い。
なぜなら、次のような計算を必要とするからだ。
$$ m^d \bmod n $$ここで
- (n=pq)
- (p,q) はいずれも数百桁の巨大素数である。
このようなべき乗演算を直接一度行うには、千桁規模の巨大整数を扱わねばならない。
中国の剰余定理はいかに高速化するか
RSA 秘密鍵は、他者が持たない情報を一つ有している。
サーバーは
$$ n=pq $$を知っている。
したがって、直接
$$ m^d\bmod n $$を計算する代わりに、より小さな二つの問題に分解できる。
まず
$$ m^d\bmod p $$を計算し、
次に
$$ m^d\bmod q $$を計算する。
この二つの法の長さは、元の半分に過ぎない。
計算速度は格段に速くなる。
最後に、中国の剰余定理を使って、二つの答えを再び
$$ m^d\bmod n $$へと組み上げる。
全体の流れは以下の通りである。
flowchart LR A["RSA 秘密鍵演算
m^d mod n"] A --> B["分割"] B --> C["法 p での演算"] B --> D["法 q での演算"] C --> E["CRT 再構成"] D --> E E --> F["最終署名/復号結果"] F --> G["HTTPS / SSH / VPN"]
これが RSA における CRT の最も有名な応用である。
なぜ劇的に速くなるのか
仮に RSA が 2048 ビットだとしよう。
すると
- p は約 1024 ビット
- q は約 1024 ビット
となる。
現代の乗算の計算量は線形ではない。
整数の長さが半分になると、計算量は通常、約四分の一にまで低下する。
四分の一が二つで、合わせて元の約二分の一。
さらに高速べき乗アルゴリズムなども考慮すると、実用上は
CRT-RSA は通常、素の RSA 秘密鍵演算より約 3～4 倍高速である。
それゆえ、ほとんどすべての RSA 実装が CRT を用いる。
もし CRT を用いなければ、サーバーの性能は大きく低下するだろう。
では何に影響しているのか
RSA 秘密鍵を使うほとんどすべての場面である。
たとえば：
- HTTPS ウェブサイト証明書
- SSH ログイン
- VPN 認証
- ソフトウェアのデジタル署名
- PDF のデジタル署名
- 電子メール暗号化（S/MIME）
サーバーが RSA 秘密鍵演算を必要とする限り、CRT はたいてい関与する。
ブロックチェーンではどうか
ブロックチェーンといえば、誰もがまず暗号通貨、ビットコインやイーサリアムを思い浮かべるだろう。しかし、これらは CRT をほとんど使わない。なぜなら、主に ECDSA（楕円曲線デジタル署名） を採用しており、RSA ではないため、CRT は中核ではないからである。
しかし、ブロックチェーン技術はデジタル署名に依存している。そしてデジタル署名には多くの実装がある。
flowchart LR A["中国の剰余定理"] A --> B["RSA"] B --> C["デジタル署名"] C --> D["HTTPS"] C --> E["ソフトウェア署名"] C --> F["認証"] C -. "現代のブロックチェーンは\n楕円曲線デジタル署名を\nより多く採用" .-> G["ブロックチェーン"]
結び
あなたは危機一髪で軍官の質問に答え、自らの身元を証明し、無事に現代へと帰還した。
身元を証明する必要があるとき、サーバーは秘密鍵を用いてデジタル署名を行う。そして中国の剰余定理は、一回の巨大なモジュロ演算を、より小さな二つの計算に分解し、その結果を再び統合することを可能にする。ほとんどすべての RSA 実装において、CRT-RSA と呼ばれるこの最適化は標準的な手法となっており、秘密鍵の演算速度を約 3～4 倍向上させている。まさにそのゆえに、二千年前に誕生した数学の定理が、今日もなお HTTPS、SSH、VPN、ソフトウェア署名といった現代インターネットの基盤の最下層で黙々と働いているのである。我々が VPN を通じて Google、YouTube、ChatGPT へアクセスできるのも、これら紙に記された古の算式に感謝せねばなるまい。
『孫子算経』のあの問題を改めて見つめてみよう。それは実のところ、「古人が計算できた」ということではない。人類はかなり早い段階から、ある種の問題は正面から力任せにぶつかる必要はないと気づいていた。回り道をして、別の角度から眺めることができる。不可視な全体を、可視な局部の集まりへと分解し、また局部から全体を再び組み立てることもできる。
人類が日付を記録し始めたその日から、今日までに一体全体何日が経過したのか、私にはわからない。その数はあまりに大きい。しかし、その数を 7 で割った余りがわかれば、今日が何曜日かがわかる。12 で割った余りがわかれば、どの月にあたるかがわかる。365 で割った余りがわかれば、一年のうちの何日目かがわかる。
