誕生日のパラドックス エクスプローラー

人を数えるのをやめて、ペアを数え始めた瞬間にこのパラドックスは解ける。23人なら誕生日は23個しか比較しないと思いがちだが、実際にはC(23,2) = 253通りの異なるペアが存在し、そのどれか一つでも一致すればよい。人間の直感は「自分と同じ人が何人いるか」という線形に増える量に注目しがちだが、本当に重要な量であるペア比較の数は、n(n−1)/2という二次関数的な速さで増えていく。だからこそ確率曲線はこれほど早く跳ね上がる — n=23ですでに50%を超え、n=57では99%を超える。これは、この問題にO(n²)個もの一致のチャンスを与えているからだ。

一致が生じるあらゆる場合を追うのではなく、このツールははるかに簡単な逆の問いを立てます。つまり「全員の誕生日が異なる確率はいくつか」です。人を一人ずつ加え、2人目は埋まった1日を避け(364/365)、3人目は2日を避け、と続けて、これら減っていく分数を掛け合わせ、100%から引きます。要点は、23人になると『全員が異なる』確率がついに半分を下回ることで、だからこそ23が転換点なのです。

同じ論理がひそかにデジタル安全性を支配しています。ハッシュ関数を破る攻撃者が特定の標的を必要とすることはまれで、同じ出力を生む任意の2つの入力さえあれば十分です。これはまさに『どれか一組』の問題です。だからN通りの出力を持つハッシュは、N回ではなく約√N回の試行で誕生日攻撃に陥ります。ゆえに256ビットのハッシュは約128ビットの衝突耐性しか持たず、設計者は長さを2倍にする必要があるのです。