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

Question

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?

Answer 1

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)