弱衝突耐性と強衝突耐性の違い【ハッシュ】

忘れそうなのでメモしておく。

例えるなら

• 弱衝突耐性･･･「ある人物と同じ顔を持つ人を探すムズかしさ」
• 強衝突耐性･･･「どんな顔でもいいので、同じ顔を持つ2人を探すムズかしさ」

みたいな感じ。

後者より前者のほうが探すのがムズかしいらしい。

というか後者は以外と確率が高いらしい。

例えば

「何人集まれば、その中に誕生日が同一の2人（以上）がいる確率が、50%を超えるか？」

という「誕生日のパラドックス」という有名な問題がある。

これはまさに強衝突耐性を試すような問題なわけだけど、これの正解は23人になるらしい。

肌感覚で言うと、100人くらいは必要な気がするけど意外にもめちゃくちゃ少ない人数でいける。

逆に

「何人集まれば、その中に自分と同じ誕生日の人がいる確率が、50%を超えるか？」

という弱衝突耐性を試すような問題の場合、正解は254人になるらしい。

引用：https://keisan.casio.jp/exec/system/1273912395

このように強衝突耐性と弱衝突耐性では、10倍近く差があることになる。

おわり