When random is not actually random enough

The blog post doesn't mention the term, but what it describes is commonly known as a "modulo bias" in cryptography.

See also: https://romailler.ch/2020/07/28/crypto-modulo_bias_guide/

A Uniform(0, 1) PRNG is the right primitive on which to base a PRNG library for arbitrary real-valued random variables because any real-valued random variable can be represented as an inverse quantile transform of a Uniform(0, 1) random variable. While I agree that only providing this primitive risks footguns as described in the article, I'm skeptical that providing a better UI alone would meaningfully reduce the risk of such footguns because availability and convenience is no guarantee of use if a prevailing attitude of users is that they know better and don't need it. Bisection search is simpler than rejection sampling or inverse transform sampling, yet it's common to see buggy, hand-rolled implementations of bisection search despite wide availability of library implementations with better UI ergonomics than PRNGs. I think wider use of fuzz testing or deterministic simulation testing really is necessary to disabuse people of that notion, along with more articles like the above explaining why hand-rolling an adapter to a uniform PRNG is a false economy compared to proven implementations with vetted statistical properties.

The thing you actually want is rejection sampling: https://en.wikipedia.org/wiki/Rejection_sampling.

That Wiki page makes it sound very complicated but for this purpose our implementation can be laughably simple which has the advantage that you know why it works and can maintain it properly with confidence.

Get suitably large inputs, for example if you're trying to pick integers between 2 and 11 inclusive, a nibble (half a byte) would be fine. Now, is the random input in the range you wanted? If so, you've got your answer. If not, throw this random input away and get more.

Too many programmers act as though random numbers were a precious resource.

I got lost when OP talked about using 10 integers to choose from 3 choices. I think I figured out what was missing in the explanation.

random_u64() Mod 3 does indeed have a single bucket that is oversized. This overweights one option by about 5×10^-20.

rand() Itself has only 32767 possible values, so it's also common for a bucket to be overweighted depending on the number of buckets.

I think this is interesting theory and fun to read about. If I was actually working with cryptography this would seem immensely important. I would also be arguing vehemently online about the std implementation of Mersenne twister and worrying about people analyzing bulk traffic with advanced scripts scraping a hundredth of a bit per sample.

But, I make games.

After finding out that trig/transcendental was basically not guaranteed to be equivalent across kernels (libc/musl), which caused the dreaded “only fails in CI” problem for me when I was trying to generate nonflat distributions of drng’s, I ended up creating https://github.com/pmarreck/random to solve it, which it did

I don’t think the “random uint” api is too low-level, or lacks a pit of success - I think you’re just reaching for the wrong api. The problem of “make n bits pseudo randomly set to either 1 or 0” is nearby to your problem of “choose an element according to a probability distribution”, but it’s a separate problem in its own right.

I think actually this is an argument for language designers to include a “std.choice” in their standard library that consumes random bytes and correctly performs common ergonomic operations like “get one element at random from this collection”.

(If your standard library tries to make a distinction between “regular random number generators” and “cryptographically secured random number generators”, I think this distinction between “generate random bits” and “make probabilistic choices” is about equally important.)

The modulo operator is not a uniform mapping; use Lemire's nearly divisionless method or simple rejection sampling and move on.

so it's not really *random* that isn't random enough - it's the operator% that worsens it

Randomness test > Specific tests for randomness: https://en.wikipedia.org/wiki/Randomness_test

Which NIST SP-800-22 implementation instead of the now-archived paranoid_crypto randomness tests?

paranoid_crypto/docs/randomness_tests.md : https://github.com/google/paranoid_crypto/blob/main/docs/ran...

/? NIST SP-800-22 Rust: https://www.google.com/search?q=NIST+SP-800-22+rust&oq=NIST+...

Sometimes it's possible to whiten random to make it uniform random or normal random;

Whitening transformation: https://en.wikipedia.org/wiki/Whitening_transformation

[flagged]

[flagged]