1
$\begingroup$

I want to generate numbers in the range $0 \leq n < 2000$ in a random order. The risk of using "generic random number generator" $\mod 2000$ is that it will cycle sooner in that range, or generate many repeated values in that range before generating new values.

How can I design a pseudorandom function that returns all of the numbers in its range over as small a domain as possible?

Ideally, $f(x)$ would be bijective for some domain $k ≤ x < k+2000$, but that may be hard to achieve, so what are some good techniques to get close to that?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

One way is

$$f(x) = \pi(x \bmod 2000),$$

where $\pi$ is a pseudorandom permutation, i.e., $\pi(\cdot)$ is a permutation on $\{1,2,\dots,2000\}$. You can build such a $\pi$ using format-preserving encryption. Search on this site and on Crypto.SE and you'll find a lot about format-preserving encryption.

That said, expecting zero collisions seems unreasonable. In practice, I expect a pragmatic answer is to just choose any hash function that works for arbitrary bit-strings, and not try to avoid having any collisions whatsoever. Treat each number as a bit-string, and has it using that hash function.

Improve this answer
$\endgroup$