韓信は本当に数学の達人なのでしょうか？古代中国の数学にヒントを得たコンピュータ暗号化アルゴリズム

この記事はAI新メディアQuantum Bit（公開アカウントID：QbitAI）より許可を得て転載しています。転載の際は出典元にご連絡ください。

意外なことに、古代の韓信の軍事視察の伝説は、後にコンピューターの暗号化アルゴリズムにインスピレーションを与えました。

伝説によると、楚漢の争いの際、韓信は1500人の兵士を率いて楚軍と戦いましたが、敗北して山に退却しました。このとき、敵軍は500人の騎兵を率いて突撃し、韓信はすぐに部隊を動員して敵を迎え撃ちました。

韓信は兵士たちに三列に並ぶよう命じたが、兵士が二人余っていた。次に兵士たちに五列に並ぶよう命じたが、兵士が三人余っていた。次に兵士たちに七列に並ぶよう命じたが、兵士がまた二人余っていた。

韓信はすぐに計算して、軍にはまだ1,073人が残っており、敵は500人以下で優勢であり、数で少数派を打ち負かしていると判断しました。そこで、彼は軍を率いて敵を破り、敗走させました。

韓信はどのようにして人数を計算したのでしょうか。また、その背後にあるアルゴリズムは、今日のコンピューター分野にどのような影響を与えているのでしょうか。そして下を見てください。

韓信も数学者ですか？

もちろん、韓信が兵士の数を計算したというのは単なる伝説であり、韓信自身は数学の達人ではありませんでした。この疑問は、韓信の死後600年以上経った1,700年前の古書に初めて登場しました。

南北朝時代には『孫子算経』にそのような問題が記録されている。 （注：この孫子は兵法書を書いた孫武ではありません）

原書にはこう書かれています。

数が分からないものがあります。3を3で数えると2つ残ります。5を5で数えると3つ残ります。7を7で数えると2つ残ります。物事の幾何学とは何でしょうか?

つまり、整数を 3 で割ると余りは 2、5 で割ると余りは 3、7 で割ると余りは 2 になります。この整数を求めてください。

これは中国剰余定理であり、「韓信の選兵問題」としても知られています。

現代数学において、中国の数学者にちなんで名付けられた重要な定理はほとんどありません。しかし、この数学定理の名前には「中国」という言葉が含まれています。

南宋時代に、中国の数学者秦九紹がこの種の問題に対する解法として「ダヤン法」を初めて提案した。

有名な数学者ガウスが同様の結果を著書で記述したのは、それから500年後のことでした。

そこで疑問なのが、伝説の「韓信」はどうやって人数を計算したのか？

「韓信の兵士選抜」問題の解決

「韓信の兵選」の問題をよりよく理解し、表現するために、「合同」という新しい数学的概念を導入します。

数学では、 a と b を正の整数 m で割った余りが同じである場合、 a と b は m を法として合同であると言われます。韓信の軍隊の選択は数式で表すことができます (X は未知数です)。

X ≡ 2 (mod 3)
X ≡ 3 (mod 5)
X ≡ 2 (7 を法として)

問題を単純化するために、最初の 2 つの合同条件のみを考慮します。3 で割ったときに 2 余り、5 で割ったときに 3 余りを満たす整数は次のとおりです。

2、5、8、11、14、17、20、23、26...
3、8、13、18、23、28、33、38...

両方の条件を満たす最初の数字は8であり、 2 番目の数字は23 であることがわかります。後続の解と前の解の差は、3 と 5 の最小公倍数である 15になります。つまり、次のようになります。

X = 8 + 15K (Kは整数)

このようにして、探している整数解を絞り込み、次に 3 番目の条件を追加して、X=8+15K を満たし、7 で割ったときに 2 余りになる数値を見つけます。

8、23、38、53、68、83、98、113、128...
2、9、16、23、30、37、44、51...

条件を満たす最初の数字は 23 で、2 番目の数字は 128 です。後続の各解と前の解との差は、3、5、7 の最小公倍数、つまり 105 になります。

解決策を見つけるこのプロセスは明らかに面倒すぎる。後に、明代の数学者程大偉がその解答を詩にまとめました。

三人が一緒に歩くと七十の稀少な梅になり、五本の梅の木には二十一の枝がある。

7 人の息子たちが再会したのはちょうど半月前です。105 で割ればわかります。

意味：

3 で割った余りに 70 を掛け、5 で割った余りに 21 を掛け、7 で割った余りに 15 を掛けます。これらをすべて足し、105 または 105 の整数倍を引きます。得られた数が答えです。

70 × 2 + 21 × 3 + 15 × 2 = 233 - 2 × 105 = 23

他の解は、23 と 105 の整数倍だけ異なります。韓信は軍隊のおおよその数を推定し、105×10+23=1073 という解を選択すべきでした。

上記の 70、21、15 の数のグループがどのようにして生まれたのかについては、興味のある読者は「中国剰余定理」の一般解をさらに読むことができるので、ここでは詳細には立ち入りません。

この「韓信の軍勢視察」問題は、軍勢の視察に使われるだけでなく、天文学や暦にも重要な応用があります。

4 年に 1 回出現し、1991 年に観測された彗星と、10 年に 1 回出現し、1997 年に観測された彗星があるとします。同じ年に彼らに次に会えるのはいつでしょうか?

X ≡ 1991 (mod 4)
X ≡ 1997 (mod 10)

計算によると、彼らが最後に会ったのは2007年で、20年ごとに再会しているので、次回は2027年になるはずです。

今日、中国剰余定理は多くのコンピュータ暗号化アルゴリズムの基礎となっており、その応用範囲は想像を超えています。

現在のコンピュータアルゴリズムに影響を与える

海外メディアQuantamagazineも「古代の戦略が現代数学に与える影響」と題した記事で、「中国の剰余定理は現代数学、コンピューターアルゴリズム、天文学などの分野に大きなインスピレーションを与える意義を持っている」と述べている。

たとえば、非常に有名なRSA 暗号化アルゴリズムは、中国剰余定理を適用します。

数論では、2 つの大きな素数を解くのは比較的簡単ですが、その積を因数分解するのは難しいことがわかっています。

RSA 暗号化アルゴリズムは、この製品を暗号化キーとして使用します。

RSA 暗号化アルゴリズムは、1977 年の誕生以来、最も広く使用されている公開鍵アルゴリズムの 1 つになりました。

さらに、中国剰余定理は高速フーリエ変換(FFT) にも適用され、離散フーリエ変換を計算するときに必要な乗算回数を大幅に削減できます。

近年、中国剰余定理は情報暗号化にも利用されています。

2018年、コロンビア大学の学者たちは、中国剰余定理を応用してテキスト内の情報を暗号化し、復元されたときに情報の正確性を確保する方法を発明した。

携帯電話をテキストに対してスキャンするだけで、アルゴリズムは暗号化された情報を提供できます。

この方法はFontCodeと呼ばれ、通常の文字に若干の調整を加え、調整された文字の情報を再エンコードして暗号化します。

例えば、次の 5 つの異なる色の「a」は、それぞれ 1 から 5 までのデジタル情報を表します。

色を使って区別しないと、肉眼で通常のフォントとの違いを見分けるのは困難です。

しかし、機械なら可能です。

アルゴリズムは、スキャンして分析するだけで、どの文字が特別に処理されているか、また、処理された文字がどのような情報を表しているかを推測できます。

したがって、一見普通のテキストでは、これらの特殊文字をうまく隠すことができ、暗号化された数字の文字列を伝えることができます。

そして、これらの数値を計算することで、伝えたい本当のメッセージを得ることができます。

しかし、この暗号化方法は十分に安全ではありません。文字が画面や紙に表示されると、その形式が多少変更される可能性があります。

ここで中国剰余定理が役に立ちます。

上記では、線形合同方程式のシステムを通じて数値を計算できることを紹介しました。

3 つの未知数を解きたい場合、3 つの線形方程式が必要です。

現在、安全を期すために、科学者たちは線形方程式の数を増やしています。

たとえば、3 つの未知数を解くには、5 つの線形方程式を立てます。5 つの方程式のうち 3 つを知っていれば、目的の答えを解くことができます。

明らかに、1,000年以上が経過しました。韓信が兵士の数を数えた時のように兵士の数を隠すことはもうありませんが、現代数学、コンピューターサイエンスなどの分野の研究者は、今でも中国剰余定理から継続的にインスピレーションを得ることができます。