7
$\begingroup$

What is a good method to generate random numbers between 0 and n from random bits?

For example, I have a one million random bits generated according to NIST SP 800 90 publications. Now I need to generate random numbers between 0 and 100 (inclusive) using these random bits. Few possible methods i could think of are

Read 7 bits, convert these to a number (0 to 127), store the number if its <= 100, otherwise :-

  • discard and move to next 7 bits e.g bits = 1111111, discard
  • take module 101 and store the number e.g bits = 1111111, store 26
  • remove most significant bit and store the number e.g bits = 1111111, store 63
  • left shift 1 bit position, read next bit and store if <=100, otherwise again left shit 1 bit position and read next bit e.g bits = 1100011, left shift 1 bit=110001, assume next bit 0, then bits = 1100010; store 98
$\endgroup$
6
  • 2
    $\begingroup$ [Edited, removing erroneous statement about NIST SP 800-90] Choice of the method depends on if you can tolerate a small theoretical bias, on if you want to minimize the number of input bits used, and if so according to what metric (worst case, average case…) and on if you can save info from one number generated to the next. $\endgroup$
    – fgrieu
    Feb 16, 2023 at 17:02
  • $\begingroup$ NIST SP 800-90 generators are cryptographically secure PRNGs? any standard for True Random Number Generators? $\endgroup$
    – crypt
    Feb 17, 2023 at 5:02
  • 2
    $\begingroup$ Correcting myself: NIST SP 800-90A is for deterministic random bit generators, NIST SP 800-90B is for entropy sources but these are not intended to be used directly as source of random bits, and NIST SP 800-90C (which AFAIK did not make it past draft so far) is for safely combining the two into a (true) random bit generator. There's also AIS31. $\endgroup$
    – fgrieu
    Feb 17, 2023 at 5:27
  • $\begingroup$ The approach of arc4random_uniform can be seen at github.com/libressl/openbsd/blob/master/src/lib/libc/crypt/… -- it avoids bias but potentially throws away lots of bits and may have to fetch additional random numbers before it can return a result. $\endgroup$
    – jcaron
    Feb 17, 2023 at 16:11

8 Answers 8

13
$\begingroup$

If you really

  • are attached to those bits so you want to use more than 101/128 of conversion attempts
  • don't want to do bignum calculations
  • want verfiable bias-free generation

then

  • collect 20 bits to make an integer between 0 and 1048575
  • reject if >= 1030301 (101^3) (happens with 1.7% probability)
  • convert the number to base 101, and use its three digits

To compare with the straightforward single digit process of taking 7 bits and rejecting numbers >= 101, if you started with 10^6 bits, then

Single digit - 10^6/7 would give you 142857 attempts of which an expected 101/128 = 112723 would be successful, giving you 750534 bits expected entropy.

Three digit - 10^6/20 would give 50000 attempts of which an expected 1030301/1048576 = 49128 would be successful, giving you 147384 output words, giving you 981314 bits of expected entropy.

The greedy might be inclined to waste only one bit rather than 20 by bumping the word along just one bit after a rejected attempt. That way lies bias! There is an optimisation in this style that allows you to check only the relevant few MSBs, the unchecked LSBs will still be truly random, however the saving in bits is typically tiny. In this case, the threshold is odd, so you would have to check down to the LSB, and no saving can be made.

101 contains 6.65821 bits, it's the largest number for which this does not exceed 6 2/3rds bits, so I wonder if the output range has been set up specifically to take advantage of this coincidence? The next number of digits to compute in one go with this method to give a further improvement is so large that there is little point in presenting it.

This method is both specific and general. The numbers above, using 20 bits to make three output digits, is specific to the 0-100 inclusive output range. However, the method, see if making n output digits in one go wastes fewer input bits, is quite general. You do not have to check every integer value of n in sequence, truncating the continued fraction expansion of the output entropy per digit gives you each successive next good value of n. It so happens that 6.658 bits is very close to a good value, and so n is very small.

$\endgroup$
1
  • $\begingroup$ Yes, this fits nicely within 32-bit arithmetic (integer division with remainder). $\endgroup$
    – hardmath
    Feb 18, 2023 at 3:02
4
$\begingroup$

I think discarding and regenerating if the result is > 100 is the best solution. Although you may have the problem that computation time varies, which could lead to side-channel attacks in a given context.

Computing modulo 100 gives every number from 0 to 27 a higher probability than the numbers 28 to 100... and I don't quite understand why you compute modulo 100 and not modulo 101 if 100 should be included.

By removing the first element, you have the same problem for all numbers from 0 to 63.

I think you have the same problem for the last method, but with a more complex set of numbers which are more likely.

An idea I had: You could create a data structure, e.g. a tree, in which you do a random search. The problem I see is that you have 101 elements, which makes it quite tricky.

$\endgroup$
7
  • 2
    $\begingroup$ any standard about generating such numbers? $\endgroup$
    – crypt
    Feb 16, 2023 at 10:32
  • 2
    $\begingroup$ Also, when you do rejection sampling, don't introduce a timing attack when you check if the number is <=100. Constant-time comparison is detailed here: crypto.stackexchange.com/questions/39429/… $\endgroup$
    – knaccc
    Feb 16, 2023 at 11:00
  • 1
    $\begingroup$ @crypt: yes there is such standard: the one you quoted, appendix A.5, which describes three different techniques (at least; it says four, but somehow I must be missing one). $\endgroup$
    – fgrieu
    Feb 16, 2023 at 17:08
  • $\begingroup$ Possible side-channel attacks: inferring RNG state based on which numbers are high (unlikely) or if n is variable, inferring n by how often the computation takes longer (more likely) $\endgroup$
    – user253751
    Feb 16, 2023 at 18:44
  • $\begingroup$ The bias when doing the modulo operation is reduced in proportion to $2^n$ if $n$ is the number of bits sampled. So for example if you sample $2^{10}=1024$ bits and compute the result modulo 100, the bias in favor of numbers in the range $0-23$ is, If I'm not wrong $100\cdot (23/1024) \approx 2.24\%$... $\endgroup$
    – Amit
    Feb 16, 2023 at 22:25
3
$\begingroup$

Posting this as an answer because nobody else cited this paper yet. In https://arxiv.org/pdf/1304.1916.pdf (Optimal Discrete Uniform Generation from Coin Flips, and Applications by Jérémie Lumbroso) we can read:

This article introduces an algorithm to draw random discrete uniform variables within a given range of size n from a source of random bits.

Below is the main algorithm reproduced.

fast dice roller

$\endgroup$
2
$\begingroup$

What is a good method to generate random numbers between 0 and n from random bits?

There are a number of known methods to convert a stream of random bits into an integer within a range; which ones are "good" would depend on what good is:

  • Simple to program
  • Have no bias (versus having a bias that's within a proscribed bound)
  • Minimize the expected number of random bits used
  • Have a bound on the number of random bits used
  • Not infinite loop if given a stream of bits that aren't random (e.g. all 1's).

Of course, some of these goals are in conflict (for example, "no bias" and "bounded number of bits used" cannot both be achieved if the size of the range isn't a power of 2).

If the main goal is simplicity (and reducing the likelihood of getting something wrong), then a straight-forward 'grab 7 bits, check if those 7 bits converted to an integer is in range, if not, try again' is good (and 'grabbing 8, discard one and then check' may be even simpler if you're in a byte-oriented environment).

On the other hand, if it is important to minimize the number of random bits used (and be unbiased), then this procedure happens to be optimal over systems that don't preserve internal state between invocations:

r := 1
a := 0
for (;;)
    a := 2*a + next_random_bit()
    r := 2*r
    if r >= 101
        if a < 101
           return a
        a := a - 101
        r := r - 101

This uses fewer than 7.5 random bits on average per element generated (which is more than 1 random bit less than the simple 'get 7 bits, reject if out of range' method).

$\endgroup$
11
  • $\begingroup$ What is this algorithm called? $\endgroup$
    – user253751
    Feb 16, 2023 at 18:49
  • $\begingroup$ @user253751: not sure, actually. I know I read it somewhere; if it was given a name, I don't remember it. $\endgroup$
    – poncho
    Feb 16, 2023 at 18:51
  • 1
    $\begingroup$ That can't possibly be correct. if r >= 101 ... r -= 101. So in the equality case we just decremented r down to zero. And doubling zero will never ever let us yield another a to the caller. We call this a "latch up" condition, where we run for a while and then get stuck. There has to be some way to stir a set bit back into r. For example, 2 * r + 1 might save this scheme. Or maybe you wanted r - 100 ? $\endgroup$
    – J_H
    Feb 16, 2023 at 19:13
  • $\begingroup$ So the intent was if r > 101 ? Ok. (That is, this scheme requires that n not be a power of 2. Cool.) $\endgroup$
    – J_H
    Feb 16, 2023 at 19:17
  • 2
    $\begingroup$ @J_H r = 101 (which actually never happens) wouldn't be a problem - we always have a < r, and so if r = 101, then a < 101, and so we'd return a value $\endgroup$
    – poncho
    Feb 16, 2023 at 19:19
2
$\begingroup$

Yep, just drop anything > 100 after having stacked seven bits.

You'll forfeit $\approx$ 21% of the available sequence, but such sequences come quickly and easily, and the unequivocal non bias outweighs the loss. You should be able to convince yourself of living with a 79% generation efficiency to get valid random numbers.

And part of that convincing comes from some of the other answers and comments thereto. Alternative generators (even if more efficacious) mean more code that has to be debugged. Also what has not been mentioned is testing. Rejection sampling is self evidently unbiased. It just works if a bit wasteful. Call that overhead insurance.

Alternative and more complex techniques will have to be tested. How? Ideally you'd perform a randomness test on the output set. Unfortunately there is no test suite that can handle an input range $0 - n, n \ne 255$. Even a mono-bit test will fail as the number of ones and zeros is meant to be uneven in this particular example, and is further confounded by Chi variation. So self designed tests become necessary. And how do you test the tests? You'd generate a reference sequence from something like $\pi$ or $e$ binary expansions, having rejection sampled them for certainly ↺

Rejection sample. It just works.

$\endgroup$
3
  • $\begingroup$ My method has 1.7 bits of overhead on average although it is not bounded, and uses the exact same methods used in rejection sampling (or simple discard method in the NIST document). You might be interested :) $\endgroup$
    – Maarten Bodewes
    Feb 16, 2023 at 23:46
  • $\begingroup$ Is this simply rejection sampling? $\endgroup$
    – qwr
    Feb 17, 2023 at 0:29
  • $\begingroup$ @qwr It is, with some statistics throw in. $\endgroup$
    – Paul Uszak
    Feb 17, 2023 at 12:36
1
$\begingroup$

The method of just discarding the numbers outside the range is the method that is, simple, easy to prove correct, adaptable, least susceptible to subtle errors, and the one you should use.

For all practical purposes, stop reading, and go to this answer and embrace its contents


What if you do want to waste as few of those bits as possible though?

What you have then is the opposite problem of an entropy coder. An entropy coder takes numbers following some statistical distribution, and turns them into a stream of bits with as close to 1 bit of entropy per bit as possible. You have a stream of 1 bit of entropy per bit, and want to turn it into numbers with some distribution, the opposite operation.

That's what the decoding part of an entropy coding scheme does.

So what you would do is do the decoding stage of arithmetic coding, give it a statistical distribution of equal weights in the range 0-100, and feed it random bits as an input instead of an encoded file.

An arithmetic coder with 31-bit symbol tables should give you a waste fraction of $\approx 2 \cdot 10^{-8}$, at which point the 32 bits of warmup padding would be the greatest source of waste for your 1 million bits.

This is not a good idea in practice:

While this conversion is reasonably fast due to entropy coders being used in performance critical software like video encoding, this speed is very often a compromise originating from the entropy coders leaking entropy in all kind of little ways.

  • This if fine for compression. Getting files a few bits larger than optimality is no big deal if decompression is quicker.
  • This is absolutely not fine for crypto! Getting subtly skewed distributions would be fatal.

I have seen non-leaky arithmetic coders, in an academic setting, maybe once or twice. I have seen dozens more leaking, both intentionally (performance) or unintentionally.

$\endgroup$
1
$\begingroup$

If you want to keep to NIST recommendations then there are the NIST algorithms in NIST SP-800 90Ar1 section A.5 "Converting Random Bits into a Random Number" (the standard that is used in the question as source for a DRBG).

The method described in the question seems similar to the "Complex Discard Method" in section A.5.2 of the NIST document. It has the disadvantage that you have to perform modular calculations, but that's fine if your $n$ is a small number like $101$. It may not be something what you want if you have an $n$ of, say, 4096 bits as for e.g. RSA-KEM though.


In general you may want to use my own solution (which I hope is at least somewhat original) called RNG-BC (random number generation using binary compare) which is very efficient while not using any big integer calculations.

I'll quickly explain the method. Let's say that a value $x$ in the range $[0, n)$ needs to be drawn. During a compare only the topmost bits of the random number $x$ are compared to $n$. If the bit in $x$ is 0 and the bit at the same position in $n$ is 1 then the number is lower and the value is accepted. If it is equal then we need to look at the next bit, and the bit in $x$ is 1 and the bit in $n$ is zero then $x$ is higher, and we need to regenerate all the bits that we've looked at. As the lower bits of $x$ are never evaluated they do not need to be replaced.

This method draws about 1.7 more bits than the bits in $n$ (obviously depending on the value of $n$), and doesn't use any special calculations, although it may require some bit buffering. There is more information and an implementation here.

Disadvantages:

  • the method isn't bounded to the number of bits it may consume. Since every bit has about half of a chance to be accepted that doesn't matter much. After about 128 bits the chances of it failing are only somewhat higher than 1 in $2^{128}$.
  • The method doesn't store any state if you need multiple random values (in the same range), so it is not optimal if you want to generate many random numbers. With just 1.7 bits of overhead that point may be moot.
$\endgroup$
0
$\begingroup$

I'll answer from the standpoint of seeking maximum performance.

Algorithm 5 of this paper is performs really well and is bias- and division-free (divisions might create a timing side channel). You can tune the parameter $L$ to consume more bits per input, while reducing the chance of a rejection.

For instance, for $L = 10$, the chance of rejection should be only $1 - 1010/1024 \approx 1.4\%$. You can quickly make three 10-bit words out of a 32 bit word by shifting and bitmasking. This wastes about 12 out of every 32 bits, or 37.5% of all bits, but also results in a low rejection rate, which translates into fewer of those costly mispredicted branches on the CPU, which result in pipeline flushes.

Note that any branch prediction scheme will necessarily fail on a rejection sampling algorithm, otherwise your bits wouldn't really be random at all. The best you can hope for, on the simple rejection scheme with 7 bits, is that the CPU always predicts "no rejection" and fails $1 - 101/128 \approx 21.1\%$ of the time. This results in a pipeline flush every 4-5 iterations, which may perform worse than the scheme suggested above. If the branch predictor tries to get too smart, mispredicted branches might happen even more often.

Do note, however, that a Monte Carlo simulation suggests you'll need $\approx 22\%$ more bits using my suggested parameters versus the simple 7-bit rejection scheme, so you'll have to balance the cost of generating these extra bits versus the cost of mispredicted branches.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.