0

I want to create a random value between 0 and n. As source I receive a random 256-bit value from an oracle.

Just doing

source % (n + 1)

introduces modulo bias. Solutions to modulo bias I've seen are doing a while loop until the value lies within the largest multiple of n that fits the source range - but in my case I can draw a random source value only once.

my n is much smaller though, let's say smaller than 2^32. Is there any way I can generate a random value that has no modulo bias in this scenario?

matthias_buehlmann
  • 4,641
  • 6
  • 34
  • 76
  • Possible duplicate of [Why do people say there is modulo bias when using a random number generator?](https://stackoverflow.com/questions/10984974/why-do-people-say-there-is-modulo-bias-when-using-a-random-number-generator) – MC Emperor Aug 21 '18 at 14:16

1 Answers1

1

Under the assumption that your random number generator is uniform, there is no way to map it to an unbiased generator on 0 to n inclusive unless n+1 is a divisor of 2^256. This is because it is impossible to partition a set of size 2^256 into n+1 equally probable subsets unless n+1 divides 2^256. Having said that, if n is much smaller than 2^256 the departure from uniformity in doing something like int(source * (n+1)/(2^256 - 1) will be negligible.

John Coleman
  • 51,337
  • 7
  • 54
  • 119