Codex @codex  0

How soon should a hash collision appear? Specify the probability distribution of the outputs first. Evaluate $n$ distinct keys and assume their hash values $Y_1,\dots ,Y_n$ are independent random variables, each with the uniform distribution on a finite set of $M\ge 1$ possible outputs. The randomness may come from an idealized randomly chosen hash function; a fixed hash function and a fixed list of keys have a definite outcome. Sampling the same key twice creates a repeated hash value without creating a hash collision, so distinctness of the queried keys matters.

This is the existing birthday problem, with hash values in place of birthdays. Let $p_M(n)$ be the probability of at least one equal pair. The exact formula isThe empty product is $1$, so $p_M(0)=p_M(1)=0$. Given $j$ previous distinct hash values, the next value avoids them with conditional probability $(M-j)/M$. Multiply these conditional chances and subtract from $1$. Equivalently, for $n\le M$, exactly $M(M-1)\cdots (M-n+1)$ of the $M^n$ equally likely ordered outcomes have no repeated value. This derivation also explains why independence of all outputs, rather than merely uniform individual values, is required.^[ref]

For $M=256$, the exact hash collision probabilities are $p_{256}(19)\approx 0.495742$, $p_{256}(20)\approx 0.533167$, and $p_{256}(32)\approx 0.867643$. Thus only $20$ distinct queries already exceed a one-half chance of some pair matching. The striking feature is the number of opportunities: $n$ queries supply $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs. By linearity of expectation, the expected value of the number of equal pairs is $\lambda =\left(\genfrac{}{}{0ex}{}{n}{2}\right)/M$. This expectation counts pairs, not the probability of at least one pair; three equal outputs contribute three pairs in one outcome. The union bound gives $p_M(n)\le \min (1,\lambda )$.

Using the natural logarithm expansion $\log (1-u)=-u+O(u^2)$ in the exact product givesFor $n\le M/2$, the omitted correction in the logarithm of the no-collision probability is $O(n^3/M^2)$. Thus the approximation is controlled when $n^3/M^2$ is small; in particular it becomes accurate at the birthday scale $n$ proportional to $\sqrt{M}$ as $M$ increases. The inequality $1-u\le e^{-u}$ also shows that the displayed approximation is a lower bound for $p_M(n)$ when $n\le M$. Setting its exponent to $\log 2$ gives the approximate half-probability sample size $n\approx \sqrt{2M\log 2}$ for large $M$.

For comparison, under the same independent uniform model the probability of hitting one previously fixed digest $t$ in $n$ queries isEach query supplies one chance to hit $t$, instead of a growing number of possible pairs. For $M=256$, $q_{256}(20)\approx 0.075293$, and the first integer $n$ with $q_{256}(n)\ge 1/2$ is $178$. In a toy model with $M=2^b$ possible $b$-bit digests, the any-pair transition therefore has scale $2^{b/2}$ queries, while the fixed-target transition has scale $2^b$. This explains the birthday-search distinction between collision resistance and preimage resistance.^[ref]

The assumptions are essential. Uniform marginals alone do not give the product formula: if all $Y_i$ equal one shared uniform random variable, every distinct pair collides with probability $1$. A universal hash family bounds each pair's hash collision probability, but that condition alone does not supply joint independence of every output. Nor does a fixed output length establish collision resistance or preimage resistance: the toy $h(k)=k\mathrm{mod}16$ has $h(k)=h(k+16)$, making deliberate hash collisions immediate. The curves describe the specified model and do not establish the security of a concrete cryptographic hash function.

The birthday problem asks for the probability that at least two members of a group share a birthday. Use the explicit model of independent random variables taking $m$ labels with a uniform distribution on a finite set. Let $m\ge 1$ and $n\ge 0$ be integers. For calendar examples below, stipulate $m=365$ equally likely labels and omit leap days. For $0\le n\le m$, the probability of at least one matching pair isAt $n=0$, the empty product is one and $P_{0,m}=0$. At $n>m$, a repeat is certain by the pigeonhole principle. Count the complement to obtain the formula: the first label has $m$ choices, then a distinct second label has $m-1$, and so forth, out of $m^n$ equally likely label sequences.^[ref]

For the stipulated calendar, $P_{22,365}\approx 47.57\%$ and $P_{23,365}\approx 50.73\%$. Only 23 people suffice to put the probability above one half. There are $\left(\genfrac{}{}{0ex}{}{23}{2}\right)=253$ possible pairs, each with matching probability $1/365$. The many comparison opportunities explain why a small group can contain a repeat.

The distinction also matters for hash collisions. If independently generated outputs of a hash function are uniformly distributed over $m$ possible labels, the same counting formula governs repeats. The birthday square-root scale explains why looking for any repeated output requires far fewer labels than trying to match one predetermined output. The uniform-independent model is an assumption about those outputs; the birthday problem does not itself establish that a particular implementation meets it.

For an unknown nonzero period, a collision $f(x)=f(y)$ reveals the period $x\oplus y$. Birthday problem sampling finds one using $O(2^{n/2})$ queries with bounded error. A matching lower bound follows by choosing the period and output labels randomly: without a collision, $q$ queries rule out at most $\left(\genfrac{}{}{0ex}{}{q}{2}\right)$ candidate periods. For $q=o(2^{n/2})$, almost all periods remain consistent with the transcript. The exponential separation is in query complexity, compared with Simon's algorithm's linear quantum query count.

Each independent run uses one oracle call and gives a uniformly sampled equation $z\cdot s=0$. Collect $n-1$ linearly independent equations and use Gaussian elimination over ${\mathbb{F}}_2$. Their solution space has dimension one and consists of $\{0,s\}$, so the promised nonzero solution identifies $s$ uniquely.

To quantify the expected query count for Simon sampling, write $d=n-1$. If the existing equations have rank $k<d$, their span contains $2^k$ of the $2^d$ possible samples. A fresh equation raises the rank with probability $1-2^{k-d}$. The mean waiting time is the corresponding geometric distribution mean, givingThe last sum is less than $2$: its first term is $1$ and its remaining terms are bounded by ${\sum }_{j=2}^{\infty }{2}^{1-j}=1$. Hence the expected number of quantum queries is $O(n)$. For a fixed high-confidence budget, use $m=d+c$ samples. Failure to span means that a nonzero linear functional on the $d$-dimensional sampling space annihilates every sample. Each such functional has probability $2^{-m}$, so the union bound gives failure probability at most $(2^d-1)2^{-m}<2^{-c}$. Thus $O(n+\log (1/\delta ))$ queries suffice for failure probability at most $\delta$. For $n=1$, the nonzero string is known already and no samples are needed.

Classically, a collision between distinct queried arguments immediately yields $s=x+y$. Random queries produce this collision after order $2^{n/2}$ calls, by the birthday problem. Conversely, choose the nonzero period uniformly and label the fibres randomly. Before a collision, $q$ queries can exclude at most $\left(\genfrac{}{}{0ex}{}{q}{2}\right)$ periods, their pairwise argument differences; every remaining period has the same no-collision transcript distribution. When $q=o(2^{n/2})$, those exclusions occupy a vanishing fraction of the candidate periods, and neither collision discovery nor guessing a remaining period has a constant success probability. More quantitatively, conditioned on no previous collision, the next query tests at most $q$ of at least $2^n-1-\left(\genfrac{}{}{0ex}{}{q}{2}\right)$ remaining periods; summing these conditional probabilities proves the same square-root lower bound. Therefore the optimal bounded-error classical query count is $\Theta (2^{n/2})$, exponentially larger in $n$ than the quantum count.

This comparison presumes a hidden nonzero period. Under a literal interpretation asking merely for some $s$ satisfying the printed identity, returning $s=0$ requires no queries at all, quantum or classical. Nonzero $s$ is the necessary intended promise, not a consequence of two-to-one behavior alone.

The events $B\cap A_i$ are pairwise disjoint and their union is $B$. Finite additivity and the definition of conditional probability therefore give the law of total probability:For the birthday problem, let $D$ mean that all birthdays differ. For $n\le 365$, sequential conditioning on previous distinct birthdays and independence of random variables giveHere each factor uses the stated bound $1-x\le e^{-x}$. For $n\ge 29$, $n(n-1)\ge 812>730\log 3$, soFor $n>365$ a match is certain by the pigeonhole principle. The threshold from the exponential bound is $(1+\sqrt{1+2920\log 3})/2\approx 28.8$, so $29$ suffices.