[Cryptography] Throwing dice for "random" numbers
Howard Chu
hyc at symas.com
Sat Aug 18 21:42:41 EDT 2018
John Denker via cryptography wrote:
> On 08/15/2018 07:20 AM, Dave Horsfall wrote:
>
>> it occurred to me that it's not as simple as it seems, with the
>> generated output (e.g. modulo 10) not being as uniform as one would
>> hope.
>
> Suppose you want decimal digits. Twelve 6-sided dice can
> be treated as a 12-digit base-6 number. In decimal that
> is a number from 0 to 2.18e9. Roll the dice. Whenever
> there is an outcome greater than or equal to 2e9, throw
> it away and re-roll. Take the result modulo 1e9. That
> gives you a uniform distribution over 9-digit decimal
> numbers, limited only by imperfections in the dice, with
> no non-uniformity introduced by the modulo operation.
>
> The same procedure generalizes to bases other than 10,
> including 2, 8, 16, and 36 or 62 (i.e. alphanumeric).
> Discarding out-of-range outcomes has been standard
> practice since the 1940s (which is kind of a long
> time in the computer business).
>
> Also, for what it's worth (which is not much): 8-sided
> dice are cheap and widely available (more so than
> 16-sided dice). You can use those to generate bytes
> or words having any integer number of bits, with no
> need to re-roll. This is not worth much because the
> inefficiency introduced by re-rolling is very small.
> It's at most a cosmetic issue, not a serious issue.
There are 10 and 20-sided dice, if you must have decimal numbers.
--
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/
More information about the cryptography
mailing list