# Why would you expect to find a collision in a hash function after approximately $\sqrt{n}$ hashes?

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.

-

## migrated from security.stackexchange.comOct 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! :) –  Rhino Oct 28 '11 at 14:05
Thanks Ninefingers –  Matt H Oct 28 '11 at 16:23

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

-
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

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

-