5

ウィキペディアで説明されている誕生日効果の解釈を手伝ってください。

誕生日攻撃は次のように機能します。

  1. 任意のメッセージ m を選択し、h(m) を計算します。
  2. リスト L を更新します。h(m) がリスト L にあるかどうかを確認します。
  3. (h(m),m) が既に L にある場合、衝突するメッセージのペアが見つかりました。それ以外の場合は、ペア (h(m),m) をリスト L に保存し、ステップ 1 に戻ります。

誕生日のパラドックスから、約 2^(n/2) 回のハッシュ評価を実行した後、一致するエントリを見つけることが期待できることがわかります。

上記は、上記のループ全体を 2^(n/2) 回繰り返すことを意味しますか (つまり、2^(n/2) はステップ 1 に戻ります)、またはすでに L にある個々のアイテムとの 2^(n/2) 比較を意味しますか? ?

4

1 に答える 1

4

これは、ループを 2^(n/2) 回繰り返すことを意味します。ただしL、ここでは通常のリストではなく、 へのハッシュ テーブル マッピングであることにh(m)注意してくださいm。したがって、各反復では、平均して一定数 (O(1)) の比較のみが必要であり、合計で O(2^(n/2)) の比較が行われます。

L が通常の配列またはリンクされたリストであった場合、反復ごとにリスト全体を検索する必要があるため、比較の数ははるかに多くなります。ただし、これはこのアルゴリズムを実装するには悪い方法です。

于 2010-05-04T16:08:17.730 に答える