# How to compute $a$ in the complex discard method of NIST SP 800-90

I've got a question about the complex discard method that has been specified in NIST SP 800-90, appendix A.5.2, steps:

1. Use the random bit generator to generate a sequence of $m$ random bits, $(b_0, b_1, …, b_{m-1})$.

2. Let $c = \sum_{i=0}^{m-1}2^i \cdot b_i$.

3. If $c < r$, then
let $(a_0, a_1, …, a_{t-1})$ be the unique sequence of values satisfying $0 ≤ a_i ≤ r -1$
such that $c = \sum_{i=0}^{t-1}r^i \cdot a_i$ else discard $c$ and go to Step 1.

OK, so step 1 is the same as generating as many bits as required for the number, i.e. $m$ bits where $m$ is the number of bits required to encode $r-1$ where $r$ is the end of the range starting at 0 (and exclusive of $r$ itself, of course).

Then step 2 is basically interpreting those bits as a number.

Now step 3 suddenly introduces a set of output values for this random number generator, $(a_0, a_1, …, a_{t-1})$. These numbers need to confirm to the condition that added together after multiplication with $r$ to the power of $i$ up to $t$ that they are equal to $c$.

Wouldn't the numbers $a_i$ be too small in that case? How can the $a_i$ values be calculated?

• Note that I made a mistaken in assuming that $m$, the number of bits to generate, was identical to the number of bits to represent $r - 1$. That would mean $c$ would be about the same size as $r$. Therefore I thought that $a_i$ could only contain small values, for more info see the answer of Poncho and my comment below it. – Maarten Bodewes Aug 1 '17 at 17:06
• And correspondingly A.5.2 step 3 is $c < r^t$ versus $c < r$ for A.5.1. – dave_thompson_085 Aug 1 '17 at 23:51

Wouldn't the numbers $a_i$ be too small in that case

No, it's just a simple base conversion; you take the integer $c$, and represent it in base $r$; the values $a_0, a_1, ...., a_{t-1}$ are the digits of the resulting conversion.

There are lots of ways to do base conversion; the simplest (if not the most efficient) would be:

For i := 0 to t-1 do
a[i] = c % r
c = c / r


(with % being the modulo operation, and / being integer division rounding down)

• Ah, wait, they redefined $m$ in A.5.2 from the definition in A.5.1: let $m$ be the number of bits in $r^t –1$. That's unfair :). Thanks for the explanation! – Maarten Bodewes Aug 1 '17 at 16:15
• With "if not the most efficient" I presume you mean that this is one of the most efficient methods, right? – Maarten Bodewes Aug 1 '17 at 17:08
• @MaartenBodewes: naah, there are more efficient (albeit more complex) methods known... – poncho Aug 1 '17 at 17:57
• Now there is an arguably less complex method known: github.com/owlstead/RNG-BC – Maarten Bodewes Mar 24 at 2:19