Modulo bias, explained
The same defect costs 4.418 bits by one measure and 0.072 bits by another. Understanding why those numbers differ by a factor of sixty is the whole lesson.
Updated 2026-09-05
The defect, in one division
You have a random byte, uniform over 0 to 255. You want a character from a 62-symbol alphabet. The obvious line is alphabet[byte % 62], and it is wrong.
It is wrong because 256 does not divide evenly by 62. Work it out: 256 = 4 x 62 + 8. Residues 0 through 7 can each be reached from five different byte values, and residues 8 through 61 can each be reached from four. The first eight characters of your alphabet come up with probability 5/256, the other fifty-four with 4/256. The ratio is exactly 1.25. The first eight characters are 25% more likely than the rest, permanently, in every string the generator produces.
Twenty million draws from a real CSPRNG mapped this way give a chi-square of 132,618.6 on 61 degrees of freedom, against a critical value of 100.888 at p = 0.999. The observed frequency of symbol zero is 0.01957428 against a theoretical 5/256 = 0.01953125, and of symbol thirty is 0.01559568 against 4/256 = 0.015625. The measured ratio is 1.255109. This is not a subtle effect that needs a large sample to see. It is visible in a histogram of a few thousand characters.
A widely repeated figure puts this bias at 1.0323x. That number is 256/248, the expected number of draws per accepted output under rejection sampling. It is a performance figure, not a bias figure, and the two get conflated constantly.
Two entropy figures that disagree by a factor of sixty
Now price the defect. Both numbers below are computed from the same distribution: eight symbols at 5/256 and fifty-four at 4/256.
Shannon entropy is the expected value of minus log of the probability, averaged over the whole distribution. Uniform over 62 symbols it is log2(62) = 5.954196 bits per character. Under the biased distribution it is 5.949690. The loss is 0.004506 bits per character, which over a sixteen-character string is 0.072 bits. That is nothing. Rounded to two decimal places it does not exist.
Min-entropy is minus log of the largest probability. It ignores the average entirely and looks only at the most likely outcome. The largest probability here is 5/256, so the min-entropy is 5.678072 bits per character, down from 5.954196. The loss is 0.276124 bits per character, and over sixteen characters it is 4.418 bits. The attacker's best-first search space has shrunk by a factor of about 21.
The reason for the gap is that the two quantities answer different questions. Shannon entropy answers how many bits you need on average to encode the output, and averages are robust: shifting a small amount of probability mass between symbols that are all still roughly equally likely barely moves an average. Min-entropy answers how much work an attacker faces if they guess in the smartest possible order, starting with the most likely value and working down. That question does not care about the average at all. It cares only about the top of the distribution, and the top of the distribution moved by the full 1.25 factor.
Put concretely: an attacker enumerating candidates for a sixteen-character token does not sample uniformly. They start with strings made entirely of the eight over-represented characters. Shannon entropy has no opinion about that strategy. Min-entropy is the measure that prices it, and it is therefore the measure a security tool must display.
| Measure | Uniform | Biased | Loss per character | Loss over 16 characters |
|---|---|---|---|---|
| Shannon entropy | 5.954196 bits | 5.949690 bits | 0.004506 | 0.072 bits |
| Min-entropy | 5.954196 bits | 5.678072 bits | 0.276124 | 4.418 bits |
Rejection sampling, and what it actually costs
The fix is to throw away the draws that cause the imbalance. Compute the largest multiple of n that fits in your draw range, discard anything at or above it, and take the modulo of what survives. Every residue below the threshold then has exactly the same number of preimages, so the output is exactly uniform. Not approximately, not negligibly close. Exactly.
With 32-bit draws instead of bytes, the arithmetic becomes almost free. For a 62-character alphabet, 2^32 = 69,273,666 x 62 + 4, so the threshold discards exactly four values out of 4,294,967,296. That is one extra draw roughly every 1.07 billion, an acceptance rate of 0.99999999. For alphabets of 16, 32 or 64 symbols the threshold is 2^32 itself and the rejection rate is exactly zero, because a power of two divides evenly and you can replace the modulo with a bitmask.
The same sampler has to be used everywhere, not just for character selection. A Fisher-Yates shuffle that draws its indices with a biased sampler reintroduces the problem in the shuffle. The naive shuffle variant that draws an index over the whole array on every iteration is separately broken: it has n^n execution paths and n! does not divide n^n for any n above two, so by the pigeonhole principle some permutations are strictly more likely than others. At n = 3 the six permutations land at {5,5,5,4,4,4} out of 27, a 25% spread between the most and least likely.
Lemire, and why we do not ship it
Daniel Lemire published a nearly-divisionless method in ACM Transactions on Modeling and Computer Simulation 29(1) in 2019. The idea is elegant. Multiply the random draw by n as a double-width product. The high word is your index. The low word tells you, without a division, whether this draw falls in the region that would cause bias, and only in the rare case where it might do you compute a single modulo to check. In C, where the double-width multiply is one instruction and the division is twenty to forty cycles, this is a real speedup and it is the right implementation.
In JavaScript the calculus inverts. There is no native double-width integer arithmetic to lean on, the emulation costs more than the single modulo it was meant to replace, and the actual bottleneck in a string generator is not the sampler at all. It is building the string. Shipping Lemire here would be a slower implementation chosen because it is a better implementation somewhere else.
The honest summary is that the method is worth understanding and not worth shipping in this language. That is a different statement from the one you usually see, which is either that Lemire is universally better or that it does not matter.
Why "just draw wider" is not good enough
A common response is that a 32-bit or 64-bit draw makes the bias unmeasurable, so you may as well use a plain modulo. It is true that the bias becomes unmeasurable. At 32 bits over a 62-character alphabet the probability ratio is 1.000000014 and the min-entropy loss over sixteen characters is about 3.1 x 10^-7 bits. Nobody will ever detect that, and no attacker will ever exploit it.
We still reject it, for two reasons. The first is that the widening argument is a claim about magnitude, and magnitude arguments have to be re-checked every time an assumption changes. Widen from a byte to a 32-bit word and the bias is negligible. Ask for an alphabet of a million symbols, or move to a 16-bit draw because it was convenient, and it is not. Rejection sampling is correct for every n up to 2^32 minus one without anyone having to re-derive the bound.
The second is more direct. When rejection costs four values in four billion, the entire argument for the shortcut is that four in four billion was too expensive. It is not. A tool whose stated position is provable uniformity does not get to make an approximation this cheap and then explain in the FAQ why it was fine.
The jam.dev generator, which currently ranks first for the head term, does exactly this: it draws a Uint32 from getRandomValues and applies a plain modulo. On its 91-character pool, 2^32 mod 91 = 74, so the first 74 characters are over-represented by roughly 0.00000212%. This is a rigour point and not a security problem, and it should never be presented as one. It is worth noting that their Fisher-Yates implementation is correct, which is more than can be said for many.
None of pinetools, codebeautify or textfixer has modulo bias. All three use the multiply-and-truncate mapping, which is uniform to within about 2^-47. Their defect is Math.random, and alleging bias against them as well would be false.
What we publish for our own output
The sampler on this site draws 32-bit words from a pooled getRandomValues buffer and applies the rejection threshold above. Four hundred thousand strings of length sixteen over a 62-character alphabet, which is 6.4 million characters, give an aggregate chi-square of 72.332 on 61 degrees of freedom against a critical value of 100.888. The pooled per-position chi-square is 969.58 on 976 degrees of freedom against 1118.25. Adjacent repeats came in at 96,642 observed against 96,774.2 expected, a z-score of -0.428.
The comparison worth putting side by side is 72.3 for the correct sampler against 132,619 for the naive byte modulo, on the same entropy source and the same alphabet. One of those numbers is a passing test and the other is a defect visible from orbit.
We also test in the other direction. A chi-square far below the lower critical value means output that is suspiciously too uniform, which is its own bug class and usually means something is not drawing fresh entropy. The pass condition is two-sided.
Doing this in your own code
The bias, computed rather than asserted
// 256 = 4*62 + 8. Residues 0..7 get five preimages, 8..61 get four.
const p = i => (i < 8 ? 5 : 4) / 256;
let shannon = 0;
for (let i = 0; i < 62; i++) shannon -= p(i) * Math.log2(p(i));
const minEntropy = -Math.log2(5 / 256);
const uniform = Math.log2(62);
// uniform 5.954196 bits
// shannon 5.949690 bits loss 0.004506 per character
// minEntropy 5.678072 bits loss 0.276124 per character
// over 16 characters: Shannon 0.072 bits, min-entropy 4.418 bitsRejection sampling, 32 bit
// limit is the largest multiple of n at or below 2^32, so every residue
// below it has exactly floor(2^32 / n) preimages. Values at or above limit
// are discarded, never folded back in. Output is exactly uniform.
function randomIndex(src, n) {
if (n === 1) return 0;
if ((n & (n - 1)) === 0) return src.next() & (n - 1); // power of two: no rejection
const limit = 4294967296 - (4294967296 % n);
let x;
do { x = src.next(); } while (x >= limit);
return x % n;
}
// n = 62: 2^32 = 69273666 * 62 + 4
// exactly 4 of 4294967296 draws are rejected
// one extra draw every 1,073,741,824 on averageFor n = 16, 32 and 64 the power-of-two branch runs and the rejection rate is exactly zero.
Fisher-Yates, the version that is actually uniform
// j is drawn from [0, i] INCLUSIVE and shrinking, giving n! execution
// paths in bijection with the n! permutations.
// The common broken version draws j from [0, n-1] every iteration: n^n
// paths, and n! never divides n^n for n > 2. At n = 3 the six outcomes
// land at {5,5,5,4,4,4}/27, a 25% spread between most and least likely.
function shuffleInPlace(arr, src) {
for (let i = arr.length - 1; i > 0; i--) {
const j = randomIndex(src, i + 1);
const t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
return arr;
}Questions
Does modulo bias actually let an attacker break anything?
By itself, at the scale of a single byte modulo over a 62-character alphabet, it costs about 4.4 bits of min-entropy over sixteen characters. A 95-bit token becomes a 91-bit token. That is not a break. It is an unnecessary and completely avoidable loss in a tool whose entire job is to produce the number it claims to produce.
Why is my generator fine if it uses Math.floor(Math.random() * n)?
That mapping is not modulo bias. Math.random returns a double with 53 bits of mantissa, so scaling and truncating is uniform to within roughly 2^-47 for any realistic n. It is uniform and predictable, which is the opposite defect and a much more serious one.
Should I use Shannon entropy or min-entropy on a strength meter?
Min-entropy, under every active constraint, with the number shown rather than a colour. For a perfectly uniform generator the two are identical, so nothing is lost. The moment anything skews the distribution they diverge, and min-entropy is the one that tracks what an attacker can do.
Does rejection sampling make generation slower in any noticeable way?
No. At 62 symbols four values in 2^32 are rejected, so on average one extra draw happens every 1.07 billion. For 16, 32 and 64 symbols the rejection rate is zero and the modulo is replaced by a bitmask. The measurable cost of correctness here is zero.
Is rejection sampling the same as rejecting whole strings that fail a rule?
They are different applications of the same principle. Rejection sampling makes a single character draw uniform. Whole-string rejection, where you generate a complete string and discard it if it fails a rule such as must contain a digit, makes the output uniform over the set of valid strings. Both work because discarding is uniform and patching is not.