random number generator - Does using modulo (%) affect quality of randomness? - Cryptography Stack Exchange
The 2026 Annual Developer Survey is live—
take the Survey today!.
Stack Internal
Knowledge at work
Bring the best of human thought and AI automation together at your work.
Explore Stack Internal
Does using modulo (%) affect quality of randomness?
Ask Question
Asked<br>11 years, 4 months ago
Modified<br>7 years, 5 months ago
Viewed<br>8k times
13
$\begingroup$
I'm writing a small script that generates random non-signed decimal integers within a certain range of values. I'm using GNU od, with the following command:
od /dev/hwrng --address-radix=n --read-bytes=4 --format=u4
/dev/hwrng is linked to a SoC thermal noise sensor (bcm2708 on Raspberry Pi), so it would return pure random bits.<br>Once obtained a pure random integer from od, I would use the modulo operator (eg: % in C/C++) to restrict the range of values (eg: 96-127). I have some doubts:
Does modulo affect the quality of randomness, faking in some way the distribution of values?
I'm not sure whether bits gathered from /dev/hwrng can be considered truly random, but I guess so, since its entropy is based on a physical phenomenon
Can I use 2 bytes instead of 4 bytes as int size, assuming that the needed range of generated values is low (eg: maximum value = 200)? I mean, probably 2 bytes are enough for small numbers. I ask this, because of the question (1): probably using bigger ranges in od results in higher quality of randomness when using modulo
Is using /dev/hwrng only for the seed value still true randomness? I would use the default PHP rand() as PRNG.
random-number-generator<br>cryptographic-hardware
Share
Improve this question
Follow
edited Jan 1, 2019 at 8:03
kelalaka
50.2k1212 gold badges126126 silver badges220220 bronze badges
asked Feb 4, 2015 at 18:23
user21698
$\endgroup$
$\begingroup$<br>Read this. Forget about /dev/hwrng, that's none of your business as an application writer: just use /dev/urandom. (And don't use PHP's rand anywhere near cryptography.)<br>$\endgroup$
Gilles 'SO- stop being evil'
Gilles 'SO- stop being evil'
2015-02-05 22:44:51 +00:00
Commented<br>Feb 5, 2015 at 22:44
$\begingroup$<br>Yes modulo affects the distribution: it's not uniform if range is not a multiple of the generator's range. Hopefully, it exists many ways to avoid the issue, see Efficiently Generating a Number in a Range for some examples<br>$\endgroup$
Yann Droneaud
Yann Droneaud
2022-08-02 10:45:43 +00:00
Commented<br>Aug 2, 2022 at 10:45
Add a comment
2 Answers 2
Sorted by:
Reset to default
Highest score (default)
Date modified (newest first)
Date created (oldest first)
17
$\begingroup$
Let me begin by saying that if you have a hardware source of randomness, you don't need to be stingy with it.
1) Does modulo affect the quality of randomness, faking in some way the distribution of values?
Yes, it does. Or at any rate, it can --- see my answer to (3) below for more details. (I'm assuming by "quality of randomness", you specifically mean that each possible output should be equally likely, and every output should be independent of the others.)
For example, let's say that you wanted to generate a random integer between zero and three. If you did this by rolling a fair six-sided die (with sides labeled zero through five) and taking the result modulo four, what would the resulting distribution look like? Well, rolling either a 0 or a 4 would cause you to output 0, so the probability of outputting a 0 would be 2/6. On the other hand, the only way you'd output a 3 would be if you actually rolled a 3. So the probability of outputting a 3 would be 1/6. This means that you'd output a 0 twice as often as you'd output a 3.
2) I'm not sure whether bits gathered from /dev/hwrng can be considered truly random, but I guess so, since its entropy is based on a physical phenomenon.
The term "truly random" usually means by definition based on some physical source of randomness. But truly random doesn't imply uniformly random. In the example above, the output of a dice roll modulo four was truly random, but some outputs were more likely than others. Physical processes rarely produce a uniform distribution. They have biases -- for example, they might produce a normal distribution -- and often have state (leading to correlations).
It's possible to transform true randomness into uniform randomness using so-called randomness extractors (aka entropy extractors). It's possible that an extractor is already built into the bcm2708. But I'm not aware of any documentation that establishes this.
Various /dev/random implementations include (attempts at) randomness extractors internally. If you trust these algorithms, you can always read bits from /dev/hwrng into /dev/urandom, and then read from /dev/urandom.
3) Can I use 2 bytes instead of 4 bytes as int size, assuming that the needed range of generated values is low (eg: maximum value = 200)? I mean,...