# Efficient way of generating a random number of N (less than 64) bits with exactly M bits equal to one [closed]

Would there be an efficient way to implement a function with the following signature:

unsigned long long int random_word(size_t n, size_t m)


that would generate a random machine word (64 bits here) such that exactly m bits over the n least significant ones at set to 1. For example: random_word(10, 3) would generate a 64-bit random number such that 3 bits over the 10 LSBs are set to 1. For a given n and m every possible output should have equal probability (uniform distribution of possible permutations).

If assembly bit twiddling hacks to do that are known, great, if not, I am looking for references and research directions.

• If the percentage of samples that match the requirement from the full range of numbers isn't too small, then rejection sampling should work (only needs to be done on those n bits, the prefix can be randomized once and then you rejection sample the n bits) – Natanael Aug 20 '19 at 19:20
• Seems more like a programming challenge than crypto-related. Define "efficient":. Code size? Minimal number of uniformlly random bit used? Is that on average, for the first call, or..? Speed: for the first call, for a million calls with the same n,m..? Is the time to generate uniform random bits counted in the performance? – fgrieu Aug 20 '19 at 19:20
• Why do you need this in cryptography? – Conrado Aug 20 '19 at 19:25
• There's actually a second way that's likely more efficient (at least when m is far from n/2). Generate 64 minus n bits of random bits for the prefix, then simply generate a bitstring of m 1's and n-m 0's, and then you perform a randomized bitwise sort (with some random sort algorithms with a sufficiently small bias, using a unique random seed), and concatenate the two strings. – Natanael Aug 20 '19 at 19:44
• Drawing an error vector of a prescribed length and Hamming weight is one of the steps in the McEliece cryptosystem. – Squeamish Ossifrage Aug 21 '19 at 16:57

I'd guess that you can simply split this into two problems:

1. create 64 - n random bits, call this R
2. shuffle n bits where m bits (at any location) are set to 1, call this P

Finally you can simply perform R | P (presuming big endian notation).

Shuffling lists of elements is an operation present in almost any language. If there is any inefficiency it would be in the shuffling algorithm (although Fisher-Yates is optimal, so you'd expect some form of that algorithm, possibly the inefficiency is getting values in a range...).

• I'm thinking that you could also just generate a value x within of 0..n - i where i goes from 0 to m, where you set the x'th bit that is not set. That would be equivalent and easier to implement. – Maarten Bodewes Aug 20 '19 at 23:39
• Actually, I've proven both experimentally and theoretically that the method in the above comment should not introduce bias (this is easy enough to prove). – Maarten Bodewes Aug 23 '19 at 5:38

The problem for choosing $$k$$ bits from $$64$$ ultimately comes down to computing a uniformly random integer $$r$$ with $$0 \leq r < \frac{64!}{k!(64-k)!}$$ then decoding it to determine which bits. The $$k!$$ in the denominator is annoying, but we can ignore it, because we can just allow our algorithm to have $$k!$$ random numbers that map to the same output (setting bit 0 then bit 4 is the same as setting bit 4 then bit 0). Now we just have multiplying a decreasing sequence starting from $$64$$: with $$k=4$$ this equals $$64 * 63 * 62 * 61$$.

So for efficiency, you select a random number in $$0 \le r_0 < 64$$, then another $$0 \le r_1 < 63$$ ... through $$0 \le r_{k-1} < 64-(k-1)$$ each time using $$r_n$$ to select among the remaining unset bits.

I threw the following Python code together showing the idea, though it's not fast or anything:

# b = size of integer type
# n = number of set bits
# random_limited(x) is some function returning [0, x) sufficiently uniformly
def random_n_set_bits(b, n):
assert b > 0
assert n >= 0 and n <= b
result = 0
available = list(range(b))
for i in range(n):
index = random_limited(len(available))
bit = available[index]
available = available[:index] + available[index + 1:]
result |= (1 << bit)
return result