3 ms·

A cleaner example without bit masking: https://github.com/openbsd/src/blob/master/lib/libc/crypt/arc4random_uniform.c https://github.com/openbsd/src/blob/master

• fanf2 4y ago
  I was hoping for a mention of Daniel Lemire’s nearly-divisionless algorithm for unbiased sampling. I recently replaced BIND’s copy of OpenBSD arc4random_uniform() with Lemire’s algorithm https://gitlab.isc.org/isc-projects/bind9/-/blob/main/lib/isc/random.c#L150 https://gitlab.isc.org/isc-projects/bind9/-/blob/main/lib/is... and I blogged on the subject a couple of times https://dotat.at/@/2020-10-29-nearly-divisionless-random-numbers.html https://dotat.at/@/2020-10-29-nearly-divisionless-random-num... https://dotat.at/@/2022-04-20-really-divisionless.html https://dotat.at/@/2022-04-20-really-divisionless.html
  • anomalroil 4y ago
    Lemire's technique is really nice, in general a good thing to learn about, since it's a bit mind bending how it's playing with intervals. Sadly last time I benchmarked it in code on x86-64 for cryptographic purposes, it wasn't faster than rejection sampling, or just using a large value and a modulo reduction: in all cases what is actually taking a lot of time is the call to get good quality randomness out of a CSPRNG, the rest being negligible in comparison.