衝突の数学：誕生日パラドックスからハッシュセキュリティまで

「衝突（collision）」という概念は、確率論とコンピュータサイエンスの両方において中心的な役割を果たします。小さな部屋にいる二人が同じ誕生日を共有している場合でも、セキュリティシステムにおいて異なる二つの入力が同じハッシュ値を生み出す場合でも、その根底にある数学は同じです。これらの確率を理解することは、しばしば直感に反するため、一般に「誕生日パラドックス」として知られています。

この記事では、誕生日問題の数学的基礎、リチャード・フォン・ミーゼスによって導入された特定の確率から一般の確率への転換、そしてこれらの概念が現代のサイバーセキュリティやハッシュテーブルの効率性にどのように適用されるかを探ります。

誕生日パラドックス：なぜ23が魔法の数字なのか

一見すると、部屋に23人いれば、二人が同じ誕生日である確率が50%になるという考えは、間違っているように思えます。直感はしばしば歪められます。なぜなら、私たちは「自分」の特定の誕生日を誰かと共有している確率について考えてしまうからです。しかし、このパラドックスは、「誰か」の二人が「任意の」誕生日を共有している場合を考えるときに発生します。

これを計算するには、逆の確率、つまりグループ内の誰も誕生日が重ならない確率を見つける方が簡単です。$n$人のグループの場合：

最初の人は、どの誕生日でも構いません (365/365)。
二人目は、一人目とは異なる誕生日である必要があります (364/365)。
三人目は、最初の一人と二人目とは異なる誕生日である必要があります (363/365)。

$n=23$の場合、すべての誕生日がユニークである確率は約49.3%であり、これは少なくとも一回の衝突が起こる確率が50.7%であることを意味します。あるコミュニティメンバーが指摘したように、このパラドックスの「驚き」は、対象が「あなた」という特定の個人から、グループ内の「任意の二人」へとシフトしていることに起因します。

範囲の拡大：占有確率

ペアの計算は単純ですが、60人のグループの中で三人が同じ誕生日である確率といった、より複雑な衝突の確率を決定することはより困難です。1930年代の保険数学局による初期の試みでは、非常に低い確率（数千分の一）という結果になることがよくありました。これは、彼らが「特定の、あらかじめ選ばれた日」に三人が集まる確率に焦点を当てていたためです。

1939年、数学者のリチャード・フォン・ミーゼスは、視点を「占有確率（occupancy probability）」へと転換させました。特定のボックス（日）に三つのボール（人）が入っているかどうかを問うのではなく、フォン・ミーゼスは、すべてのボックスを調べ、三つ以上のボールが入っているボックスがいくつあるかを数えることを提案しました。

これを期待値 $E(x_s)$ として扱うことで、数学は大きく変わります。60人のグループの場合、三つの一致（triple match）の期待確率は約0.22です。これは、およそ4〜5組の60人グループの中で、三人の誕生日が一致するケースが発生することを意味します。これは、以前の計算よりもはるかに一般的な出来事です。

コンピュータにおける実世界の応用

この数学的枠組みは、単なる好奇心の対象ではありません。コンピュータサイエンスにおけるデータの扱い方の基礎となっています。

ハッシュテーブルの衝突

ハッシュテーブルにおいて、「日」はテーブルのフィールドになり、「人」はハッシュ値になります。誕生日問題を用いて、開発者は選択したテーブルサイズとエントリ数に基づいて、発生する衝突の数を近似的に見積もることができます。これは、テーブルのパフォーマンスを維持するために極めて重要です。衝突が多すぎると、検索速度が低下するためです。

サイバーセキュリティにおける誕生日攻撃

セキュリティの分野において、「誕生日攻撃（Birthday Attack）」は、暗号学的ハッシュ関数における衝突を見つけるための総当たり攻撃の一種です。攻撃者は特定のハッシュ値が現れるのを待つのではなく、単に、任意の二つの入力が同じ出力 produce します、つまり、任意の二つの入力が同じ出力を生成するまで、ランダムな入力を生成し続けます。

RNGの欠陥の検出

セキュリティの枠組みを超えて、これらの原理は乱数生成器（RNG）のテストに使用されます。周期が $2^{32}$ の完全に分散されたRNGは、最初の $2^{32}$ 個の出力で衝突がゼロであるはずです。しかし、真にランダムな数列は、わずか200,000個の出力の後に約100個の衝突が発生することが期待されます。この不一致は、エンジニアが、RNGがランダムに振る舞うのではなく、その状態の1対1の置換（permutation）を返しているかどうかを検出するのに役立ちます。

結論

誕生日問題は、衝突は私たちの直感に反してはるかに起こりやすいということを教えてくれます。特定のターゲットを向いた視点から、全般的な占有へと視点点を移すことで、私たちは、部屋の人口統計から、世界で最も機密性の高いデータのセキュリティまで、複雑なシステムの挙動をうに対して予測することが可能になります。