Engineering / Mathematics — Probabilistic Algorithms
Generating a Random Number from a Given Interval
Sampling uniformly from an arbitrary range using a source of random bits, and controlling the resulting bias.
Executive summary
A source of uniform bits generates uniform values on powers of two. Producing a uniform value on an arbitrary range requires either rejection sampling, which is exact, or reduction, which is biased.
The bias from reduction is quantifiable and can be driven below any threshold by drawing extra bits.
Learning objectives
- Implement rejection sampling and bound its expected cost.
- Quantify the bias of the modular reduction method.
- Choose between the two approaches.
01Rejection sampling
Uniform sampling by rejection
bound n, source of uniform bitsuniform value in [0, n)- Let k be the number of bits such that 2^k ≥ n.
- Draw k uniform random bits, forming a value v in [0, 2^k).
- If v < n, return v.
- Otherwise discard v and repeat.
expected fewer than 2 iterationsThe output is exactly uniform, with no approximation. The acceptance probability is n/2^k, which exceeds one half by the choice of k, so the expected iteration count is below two.
02Reduction and its bias
Drawing a k-bit value and reducing modulo n is bounded-time but not uniform: residues below 2^k mod n occur once more often than the rest.
Bias bound
The statistical distance between (uniform k-bit value) mod n and the uniform distribution on [0, n) is at most n / 2^k.
| Excess bits k − len(n) | Bias bound | Suitable for |
|---|---|---|
| 0 | ≈ 1 | Nothing |
| 8 | 2^{−8} | Non-critical sampling |
| 64 | 2^{−64} | Most cryptographic uses |
| 128 | 2^{−128} | High-security parameters |
Drawing 64 or 128 bits beyond the length of n makes the bias negligible while keeping the operation bounded-time, which is why this is the standard approach in cryptographic libraries.
03Choosing between them
Rejection
Exactly uniform, simple to reason about, unbounded time. Right where exactness matters and timing is not observable.
Reduction with excess bits
Bounded time, negligible bias, slightly more expensive per draw. Right for constant-time cryptographic code.
04Frequently asked questions
Why is the acceptance probability above one half?
Because k is chosen minimally with 2^k ≥ n, so n > 2^{k−1}, giving n/2^k > 1/2. A larger k would lower acceptance and raise the expected iteration count.
Can rejection sampling be made constant-time?
Not while remaining exact. Fixing the iteration count reintroduces a failure probability, converting it into a bounded-time method with residual bias — essentially the reduction approach in another form.
Does the bias matter outside cryptography?
Rarely. For simulation and randomised algorithms a bias of 2^{−8} is immaterial. It matters where an adversary can accumulate many samples and exploit a systematic skew.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 159-162.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.