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

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

  • 弱衝突耐性:あるハッシュ値を持つデータの作りにくさ。
  • 強衝突耐性:同じハッシュ値をもつ2つのデータの作りにくさ。

 

例えるなら

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

みたいな感じ。

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

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

 

例えば

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

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

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

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

 

逆に

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

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

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

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

 

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

 

おわり

暗号
スポンサーリンク
この記事を書いた人
penpen

1991生まれ。
2019年くらいからフロントエンドエンジニアを目指している元アフィリエイターです💩

penpenをフォローする
penpenをフォローする
penpenメモ

コメント

タイトルとURLをコピーしました