I have a discrete randomness source that emits random integer numbers in range [0..N) with uniform distribution. I need to reduce this distribution, limiting it to [0..M), where M <= N, but keep it both integer and uniform.
I can't think of approaches that would work for N % M != 0. For example, for N = 100 and M = 99, if projection function is f(x) := x % M, it appears that zero is rolled out twice more often than any other value, because both f(0) = 0 and f(99) = 0. For f(x) := floor(M * x / N) it's the same — these methods induce aliasing, which is strictly unwanted.
Of course, I could try to select such M' for which N >= M' >= M, N % M' == 0 and M' % M == 0, and just retry getting random value from source each time random value is larger than M', but I don't like this approach, as it has big chance to just waste randomness.
Is there maybe more correct solution to this problem?
What I am trying to do is distributed random number generation — I get random bitstring of fixed length L after collecting and processing every response, which can be seen as an integer number in range N=2**L, [0..N). Application may not need such large numbers, it may desire random number in range [0..M), so I need to somehow truncate what I have to what I need, and that's what this question is about.