Some example code.

[Paul Martin]

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.co.uk>
Simtec Electronics         Tel: +44 1772 978010
http://www.simtec.co.uk/   Fax: +44 1772 816426