Some example code.

[Nicolas Lynch-Aird]

Hi Paul,

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. 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.

I also wonder, but I do not know, if only discarding one byte each time the
while loop fails to find a valid value is entirely valid. In my own code (in
the ekey_get_int_range() function available at
https://bitbucket.org/entropykeywin/entropykey-win/src/19e894448a6a/Driver/E
ntropyKeyDLL/entropykey/src/entropykey.cpp?at=default ) I have been more
cautious and ensured that I always take the same size chunk of (new) entropy
from the source for every trial - and if the number obtained is outside the
required range I bin the whole lot and start again. 

Nicolas Lynch-Aird




-----Original Message-----
From: entropykey-users-bounces at lists.simtec.co.uk
[mailto:entropykey-users-bounces at lists.simtec.co.uk] On Behalf Of Paul
Martin
Sent: 02 November 2012 21:23
To: entropykey-users at lists.simtec.co.uk
Subject: Some example code.

I was looking into a customer query earlier today, and came up with
the following which might be useful to people.

It's crude, but it demonstrates how you might transform entropy from a
byte source into random integers between 0 and n-1.

-- 
Paul Martin <pm at simtec.co.uk>
Simtec Electronics         Tel: +44 1772 978010
http://www.simtec.co.uk/   Fax: +44 1772 816426