Birthday Collision Threshold

For a hash with b output bits, the birthday bound approximates the collision probability after q random samples as:

p ~= 1 - exp( - q (q - 1) / (2 * 2^b) )

Your job is to compute the minimum integer q such that p >= target. Use the approximation above (not the exact combinatorial formula).

Function signature

func MinSamplesForCollision(bitStrength int, target float64) int

Constraints

• 1 <= bitStrength <= 256
• 0 < target < 1

Notes

• Use float64 math. math.Ldexp(1, bitStrength) is a stable way to compute 2^b as a float.
• The formula can be rearranged: q = ceil( (1 + sqrt(1 + 4t)) / 2 ) where t = 2 * 2^b * ln(1/(1-target)).