Unbiased Modulo Reduction

A common mistake in cryptographic code is mapping a random 64-bit value to [0, n) by x % n. This is biased unless 2^64 is divisible by n.

To avoid bias, use rejection sampling:

1. Let limit = maxUint64 - (maxUint64 % n).
2. Draw a random r.
3. If r < limit, return r % n.
4. Otherwise, reject and retry.

Function signature

type RNG interface {
    Next() uint64
}

func UniformMod(n uint64, rng RNG) uint64

Constraints

• n >= 1
• rng.Next() returns a uniform uint64.

Notes

• You must reject values r >= limit to remove bias.
• This is a building block for safe key/nonce generation.