Geek Answers Handbook

Can someone clarify the effect of a birthday for me?

Please help interpret the effect of a birthday as described on Wikipedia:

A birthday attack works as follows:

  • Select any message m and calculate h (m).
  • Refresh list L. Check that h (m) is on list L.
  • if (h (m), m) is already in L, a counter pair of messages is found. otherwise, save the pair (h (m), m) in the list L and go back to step 1.

From the paradox of the day, we know that we can expect to find a match after performing a 2 ^ (n / 2) hash estimate.

Does this mean more than 2 ^ (n / 2) iterations through the entire cycle (i.e. 2 ^ (n / 2) returns to step 1), OR does this mean 2 ^ (n / 2) comparisons with individual elements already in L?

+5
source share
1 answer

This means that iterations 2 ^ (n / 2) are repeated through the loop. But Lkeep in mind that this will not be a regular list, but a hash table displaying h(m)- m. Thus, each iteration will only need a constant number (O (1)) of comparisons on average, and there will be a general comparison of O (2 ^ (n / 2)).

If L was a normal array or linked list, the number of comparisons would be much larger, since you would need to search every iteration throughout the list. This will be a bad way to implement this algorithm.

+4
source

More articles:


All Articles