What is the binomial coefficient and how does it relate to cryptographic analysis?
The binomial coefficient $\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$ counts the number of ways to choose $k$ items from $n$, and it drives the probability estimates behind cryptanalysis — above all the birthday attack.
* The birthday paradox: counting $\binom{n}{2}$ pairs, a collision becomes likely after only about $\sqrt{N}$ draws. *
It shows up in cryptography wherever you count pairs or subsets. The birthday attack is the headline example: with $n$ hash outputs there are $\binom{n}{2} = \frac{n(n-1)}{2}$ possible pairs, and because that grows quadratically, a matching pair (collision) becomes likely after only about $\sqrt{N}$ tries, where $N$ is the number of possible hash values — far sooner than intuition expects.
Formula:
$$\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$$
Also written as: "$n$ choose $k$", $C(n,k)$, or "$n$ over $k$".
Examples:
$$\binom{5}{2} = \frac{5!}{2!\,3!} = \frac{120}{2 \cdot 6} = 10 \qquad\qquad \binom{8}{3} = \frac{8!}{3!\,5!} = 56$$
There are 10 ways to pick 2 items out of 5, and 56 ways to pick 3 out of 8.
Cryptographic applications:
- Calculating the probability of collisions (birthday attacks)
- Analyzing the distribution of bits in cipher outputs
- Computing probabilities in differential/linear cryptanalysis
- Understanding the birthday paradox: $\binom{n}{2} = \frac{n(n-1)}{2}$ pairs
Key property: $\binom{n}{k} = \binom{n}{n-k}$ — choosing $k$ items to include is the same as choosing $n-k$ items to exclude.
Go deeper:
Birthday attack (Wikipedia) — how the pair count makes collisions arrive near √N.