10
$\begingroup$

I can't get an intuitive understanding of why it's $2^{(\frac{n}{2})}$ and not $2^n$, where $n$ is the number of bits of which the key consists.

$\endgroup$

migrated from security.stackexchange.com Oct 28 '11 at 13:27

This question came from our site for information security professionals.

  • $\begingroup$ Hello, welcome to Crypto - you'll need to register your account here to pick up your question and rep! :) $\endgroup$ – user46 Oct 28 '11 at 14:05
10
$\begingroup$

A collision is between two values. If you take a random pair of values you get a 1/2n chance of having a collision.

With 2n/2 values you have about 2n-1 pairs, so you could expect about 1/2 chance of collision.

(That's just the "intuitive way" of thinking about it; in practice, there are mathematical details.)

$\endgroup$
  • 1
    $\begingroup$ Specifically, $k$ items form $k(k-1)/2 = (k^2-k)/2$ pairs. This formula is easily derived: each of the $k$ items can form a pair with each of the $k-1$ others, giving $k(k-1)$ ordered pairs; but each unordered pair can be ordered in two ways, so we need to divide by two. $\endgroup$ – Ilmari Karonen Oct 28 '11 at 20:17
2
$\begingroup$

I think the simple way of looking at it is that it's because the number of pairs between items is roughly proportional to the square of the number of items.

Consider:

2 items-> 1 pair:  AB
3 items-> 3 pairs: AB AC BC
4 items-> 6 pairs: AB AC AD BC BD CD
5 items->10 pairs: AB AC AD AE BC BD BE CD CE DE
6 items->15 pairs: AB AC AD AE AF BC BD BE BF CD CE CF DE DF EF
7 items->21 pairs: AB AC AD AE AF AG BC BD BE BF BG CD CE CF CG DE DF DG EF EG FG
8 items->28 pairs: AB AC AD AE AF AG AH BC BD BE BF BG BH CD CE CF CG CH DE DF DG DH EF EG EH FG FH GH

If you look at these as sequences, the parallel between number of pairs and squares is fairly direct.

For N items, the number of pairs of those items is 1+2+3+...N.

For squares, instead of adding all the numbers, you add only the odd numbers. For example, 42 = 1+3+5+7 (the first four odd numbers).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.