Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

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

This question came from our site for Information security professionals.

    
Hello, welcome to Crypto - you'll need to register your account here to pick up your question and rep! :) –  Ninefingers Oct 28 '11 at 14:05
    
Thanks Ninefingers –  Matt H Oct 28 '11 at 16:23
add comment

2 Answers 2

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.)

share|improve this answer
1  
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. –  Ilmari Karonen Oct 28 '11 at 20:17
add comment

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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