I'm trying to figure out the best way to generate a cryptographically secure random number between 0 and 200 (inclusive) from a cryptographically secure random string of bytes (ie. read from /dev/urandom or some such).

I could do random[0] % 201 but then numbers 0-54 would be more likely than 55-200 which would make the resulting number more predictable than it should be.

How can I use the random octet string to create a number in a range 0...k-1 (where k is 201)?


5 Answers 5


The method given in this other answer is correct: to choose a uniformly random integer in range $[0,k-1]$ given a string of uniformly random integers in range $[0,n-1]$ with $1<k≤n$, get one integer $x$ from the string until $x<⌊n/k⌋⋅k$, then output $y=x\bmod k$. If we have $k≤n<2k$ (as in the question where $k=201$, $n=256$), that simplifies to: get one integer $x$ from the string until $x<k$, then output $x$.

However, that's not the best method, as asked: it consumes more from the input string than strictly needed. Otherwise said, when the input string is of limited length, odds that the algorithm fails are higher than needed. If there are $m$ values in the input string, odds of failure are $(1-⌊n/k⌋⋅k/n)^m$. For $k=201$, $n=256$, $m=3$, that's nearly $1\%$. It can get much worse: for $k=129$, $n=256$, $m=3$, odds of failure are over $12\%$.

We can modify the algorithm to improve on that; and also remove the $k≤n$ requirement.

  1. Set $r←0$, $s←1$.
  2. Get one new $x$ from the random string, set $r←r⋅n+x$ and $s←s⋅n$.
  3. If $r≥⌊s/k⌋⋅k$, set $r←r-⌊s/k⌋\cdot k$ and $s←s-⌊s/k⌋⋅k$, and proceed to step 2.
  4. Output $y=r\bmod k$, and stop.

Sketch of proof of correctness: by induction, before step 2 and before step 3, $r$ is a uniformly random integer with $0≤r<s$.

The integers $r$ and $s$ never exceed $(k-1)⋅n$, and thus the algorithm does not require arbitrary-precision arithmetic. It minimize odds of failure for a given input string of length $m$, to the bare minimum possible for exactly uniform output: $(n^m\bmod k)/n^m$; that is $≈0.0009\%$ (rather than $≈1\%$) for $k=201$, $n=256$, $m=3$; or $≈0.0007\%$ (rather than $≈12\%$) for $k=129$, $n=256$, $m=3$.

The algorithm works if the input string contains bits, or dice rolls with any number of faces, including variable (just change $n$ at step 2 according to the $x$ extracted from the input string).

If we need to generate more than one output $y$, there are several options:

  • The easiest is to start over; but that's clearly sub-optimal, especially when $n≫k$.
  • We can change "stop" at step 4 to: "set $r←⌊r/k⌋$, set $s←⌊s/k⌋$ (then, if desired, change $k$ for the next output); and proceed to step 3". The resulting algorithm still produce uniformly distributed output (the recurrence in the proof sketch holds), drastically reduce the consumption from the input string when $n≫k$, but I'm uncertain about optimality is not optimal (that's blatant for $k=2$, $n=3$).
  • If we know the number $j$ of desired outputs $y$ in advance, we can set $\hat k=k^j$, generate one $\hat y$ uniform in $[0,\hat k-1]$ using the optimal algorithm, then split $\hat y$ into $j$ outputs by expressing $\hat y$ as a $j$-digit number in base $k$. That's back to optimal, but is not a sequential algorithm, and requires arbitrary precision arithmetic when $j$ grows, with $O(j)$ extra memory.
  • We can generate any number of outputs using several batches of $j$ as in the previous tweak, but using the suboptimal sequential algorithm described above. That allows using bounded extra memory, and becomes close to optimality as $\hat k=k^j$ grows. However this is not a sequential algorithm.

I now lean towards belief that any optimum algorithm is bound to require $O(\log m)$ extra memory in some worst case. However it is possible to make a sequential algorithm using bounded extra memory, much less than above, and closer to optimality. I plan to detail such an algorithm (if someone else finds a reference, or otherwise has a suitable algorithm, please tell us!).

  • 1
    $\begingroup$ i don't see how this is supposed to work. Let's say k = 140, n = 256 and the first x = 139. it'd loop at least once then per pastebin.com/zHxm9LD6. it doesn't seem like it should be looping at all, however, since 139 < 140... $\endgroup$
    – paynes_bay
    Commented Aug 2, 2013 at 20:24
  • 1
    $\begingroup$ Never mind.. floor(s/k)*k == floor(256/140)*140 == 140 - not 1. $\endgroup$
    – paynes_bay
    Commented Aug 2, 2013 at 22:26
  • $\begingroup$ The optimal solution is similar in concept to Arithmetic Coding, and in principle you can have O(1) memory requirement for the processing (but of course O(log k) to store the output. $\endgroup$ Commented Mar 18, 2015 at 15:49
  • 1
    $\begingroup$ @Neil Slater: Arithmetic coding indeed can reach optimality, or use O(1) memory and be practical. However, unless I err, arithmetic coding with O(1) memory can run into cases where it requires more bits than optimal arithmetic coding. $\endgroup$
    – fgrieu
    Commented Mar 18, 2015 at 15:58
  • 1
    $\begingroup$ @fgrieu: Actually, it's a long time since I read up on it. There are a few simple state flags, but now you mention it, there might be more - I may be forgetting how deferred resolutions of ambiguous values are stashed. I was lazy when I implemented it before, and just used big integer libraries to avoid all the bit shuffling. $\endgroup$ Commented Mar 18, 2015 at 16:10

A trivial way to achieve this is to use the number is it's smaller than 201 and discard it (move on to the the next byte) if it's not.

The derived numbers will be truly random provided that the bytes are:

Since the sequence is random, every possible value of every number in the original sequence has probability $\frac{1}{256}$. Thus, at any given point, the probability that the next byte will be $k\leq200$ is also $p_0=\frac{1}{256}$.

However, the probability that the byte will be discarded is $\frac{55}{256}$. Because of this and the fact that the numbers are independent, the probability that the second byte provides us with the number $k$ is $p_1=\frac{55}{256}\cdot\frac{1}{256}$.

Continuing this reasoning, the probability that the first $j$ bytes will be discarded and that the next byte is $k$ is $p_j=\left(\frac{55}{256}\right)\cdot\frac{1}{256}$. Thus, the probability of the next derived number being 42 is $$p=p_0 + p_1 + p_2 + \cdots = \sum_{n=0}^{+\infty}\left(\frac{55}{256}\right)^n\cdot\frac{1}{256}.$$

This is a geometric series, and the probability is $$p = \frac{1}{1-\frac{55}{256}}\cdot\frac{1}{256} = \frac{1}{\frac{201}{256}}\cdot\frac{1}{256} = \frac{256}{201}\cdot\frac{1}{256} = \frac{1}{201}.$$

Since this holds for every of the 201 possible values of $k$, the derived sequence is random.

In general, if your RNG outputs numbers $x\in\{0,\cdots,n - 1\}$ and you need to derive a random sequence of numbers $y\in\{0,\cdots,k - 1\}$, you can take $y = x\bmod k$ if $x < \left\lfloor\frac{n}{k}\right\rfloor\cdot k$ and discard $x$ otherwise.

Since $\left\lfloor\frac{n}{k}\right\rfloor\cdot k$ is an entire multiple of $k$, there is no bias.

  • $\begingroup$ Could you add a few words about why this is true? This might be of additional value to the OP, especially in cryptography you don't want to take anything for granted unless you have a proof or a solid reference. $\endgroup$
    – Thomas
    Commented Dec 15, 2012 at 17:08
  • $\begingroup$ @Thomas: I took this a premise, since the numbers of a random sequence should be completely independent, so it cannot matter which numbers we use (and in which order). But other than the quote each nameable subsequence of random sequence should be random as well from Infinity and the mind (hardly solid cryptography), I can't find any reference. $\endgroup$
    – Dennis
    Commented Dec 15, 2012 at 17:24
  • $\begingroup$ Well, yes, each number in the sequence is independent, but it may not immediately be obvious to one with little knowledge of probability why discarding a number and trying with the next (independent) one is a valid strategy. That's what I meant. By the way, did you make a typo with X < (N / K) * K? I think you meant X < K. $\endgroup$
    – Thomas
    Commented Dec 15, 2012 at 17:39
  • $\begingroup$ I think you're right Thomas in that a typo was made. With (N / K) * K the K's would cancel each other out leaving you with N, which X is already pretty much guaranteed to be less than. $\endgroup$
    – neubert
    Commented Dec 15, 2012 at 19:10
  • $\begingroup$ @Thomas: I see what you mean. I'll expand on that when I have a little more time. The division in X < (N / K) * K is integer division. If we were interested in integers below 100, we can use all X such that X < (256 / 100) * 100 = 2 * 100 = 200. With X < K, there would be no need for the modulus. $\endgroup$
    – Dennis
    Commented Dec 15, 2012 at 20:34

The answer by fgrieu is excellent as always. However, I just wanted to document an alternative approach.

If bias is small enough it is practically the same as there was no bias at all. For this reason, some standards like NIST's public key standard FIPS 186-4: Digital Signature Standard allow random number generation, where some extra octets are generated in order to reduce (but not completely eliminate) the bias. According to that document, formula B.1.2, for generation of keys to be used in DSA algorithm (common public key standard), it is thought that bias of less than $1 / 2^{64}$ is acceptable.

In other words, instead of generating just eight (8) bits, generate at least 76, and then use modulo operation. The bias will be small enough that in many purposes it cannot be seen (at least if the amount of generated random numbers is not very larger).

The benefit of accepting some bias is that the number of input bits needed is deterministic and therefore, it is possible to avoid worst cases for amount of random bits needed before output can be produced.

So in then end you could do:

random[0...8] % 201

  • $\begingroup$ This seems to be identical to the Simple Modular method in NIST SP 800-90 appendix A.5.3 as described in my new answer. Note that you indeed have to generate 9 bytes for a bias less than one-sixty-fourth. $\endgroup$
    – Maarten Bodewes
    Commented Aug 1, 2017 at 14:27
  • 1
    $\begingroup$ NIST and FIPS documents are by the same organization. These formulas are indeed the same. $\endgroup$
    – user4982
    Commented Aug 3, 2017 at 12:46
  • $\begingroup$ @MaartenBodewes Since 9 bytes is beyond the scope of UInt64, would you recommend using UInt128 or something else? For example, int randomArrayIndex = (int)(UInt128(random[0..16]) % UInt128(number)). $\endgroup$ Commented Jan 29 at 18:41
  • $\begingroup$ @samuel-lucas6 For smaller numbers I would just use the Simple Discard Method also known as rejection sampling, possibly trying to get to a value between x times the max if the max can be multiplied to a number just smaller than a power of two. For larger numbers (that are not just under a power of two) I have "my own" super cheap method called RNG-BC or the Optimized Simple Discard (average 1.7 bits overhead per value, depending slightly on the max value of course). If you're masochistic you can also use the complex discard method for multiple numbers. $\endgroup$
    – Maarten Bodewes
    Commented Jan 29 at 22:55
  • $\begingroup$ @samuel-lucas6 It depends on the use case, the memory and the speed of the RNG of course, and possibly even the CPU speed. Not sure what you want to do :) I don't particularly like the simple modular method. $\endgroup$
    – Maarten Bodewes
    Commented Jan 29 at 23:06

Various tested methods to convert bit/octet strings into random numbers are proposed in NIST SP 800-90: Recommendation for Random Number Generation Using Deterministic Random Bit Generators. They are defined in Appendix A.5:

  • A.5.1, The Simple Discard Method: generate values of the minimum of $m$ bits until you get one that is smaller than $r$ - the exclusive maximum value (i.e. the method described by Dennis in the answer here);
  • A.5.2, The Complex Discard Method: a complex method of generate a larger amount of random numbers that has a smaller chance of having to regenerate random bits.
  • A.5.3, The Simple Modular Method: generate at least 64 bits more than the minimum number of bits $m$, then return that value divided by $r$ (some skew will be present; you can also make it unbiased but non-deterministic by combining it with the simple discard method).

Obviously you can add / subtract a constant value $x$ if you want a range of $[x..n + x)$ instead of $[0..n)$.

  • 1
    $\begingroup$ I think the simple modular method is similar answer given by fgrieu. This question also provides answers for this other math question math.stackexchange.com/questions/1314460/… $\endgroup$
    – daniel
    Commented Aug 1, 2017 at 13:10

Try to use bitmasks. For example - M is your desired high limit, so use r ?< M/n as a bit mask constructing your number. And after all XOR it with one extra number from RNG.

  • 5
    $\begingroup$ Thanks for playing, but that's not enough. Only values of $2^y$ can be derived this way, and for those you can just take $y$ bits. Division does not work on bits, you cannot have partial bits. $\endgroup$
    – Maarten Bodewes
    Commented Mar 18, 2015 at 16:09

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.