0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Maarten Bodewes Aug 1 '17 at 17:06
  • $\begingroup$ And correspondingly A.5.2 step 3 is $c < r^t$ versus $c < r$ for A.5.1. $\endgroup$ – dave_thompson_085 Aug 1 '17 at 23:51
1
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Maarten Bodewes Aug 1 '17 at 16:15
  • $\begingroup$ With "if not the most efficient" I presume you mean that this is one of the most efficient methods, right? $\endgroup$ – Maarten Bodewes Aug 1 '17 at 17:08
  • 1
    $\begingroup$ @MaartenBodewes: naah, there are more efficient (albeit more complex) methods known... $\endgroup$ – poncho Aug 1 '17 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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