Some example code.

Paul Martin pm at
Mon Nov 5 13:35:59 GMT 2012

On Mon, Nov 05, 2012 at 12:08:58PM -0000, Nicolas Lynch-Aird wrote:
> I'm not sure about this part of your code:
>     value = random_pool % n;
>     random_pool = random_pool / n; /* integer divide */
>     random_bits -= bits;
> I appreciate it could be argued that you have reduced random_pool by at
> least the number of bits that have been used in the form of the returned
> value. BUT in deriving that value through the modulo operator there is
> presumably at least some degree of correlation between the upper bits of
> random_pool (which are being left for use in the next call to the function)
> and the returned value.

This is a weak area, yes.  As I said, the example code is crude.
But... that's why it's an integer divide there and not a bitshift.
That way the dividend is carried forward and the remainder is what is
returned -- the two are not correlated.

> If nothing else, this is reflected in the change in
> the probability of success on any given cycle round the while loop: the
> ratio of (maxval+1)/(INTMASK+1) gets closer to 1 as more bits or bytes are
> used. Using 31 (or 63) bits in random_pool, rather than just using the
> minimum number given in the bits variable, has in general significantly
> improved this ratio, and hence the probability of finding a valid value, on
> each cycle of the while loop - hence improving the probability of a rapid
> return from the function call. But I think if you are going to do this then
> you should also be reducing random_pool by the full number of 31 (or 63)
> bits that have been used in determining the value.

See above.  It doesn't matter that the probability of having to throw
away a value in the while loop increases: as long as the entropy
source is good, the distribution of returned values remains the same.
It's also the reason why the pool value is filled from its least
significant end.

Paul Martin <pm at>
Simtec Electronics         Tel: +44 1772 978010   Fax: +44 1772 816426

More information about the EntropyKey-users mailing list