I want an algorithm which generates random integers, without replacement, from a large range [0-N], N~10^12.

However, the whole range should not be stored in memory. The memory footprint should be O(1) relative to N. The algorithm can (probably must) retain state after every sample request.

The randomness should be "strong" in the cryptographic sense.

  • 3
    $\begingroup$ Use a block cipher. Specifically, Format-preserving encryption. $\endgroup$ Commented Mar 11, 2020 at 21:24
  • $\begingroup$ A powerful random engine that generates a random number from [1, (N+1)!] will solve this problem trivially. So is there any limit on the random engine being used? $\endgroup$
    – xskxzr
    Commented Mar 12, 2020 at 1:59
  • $\begingroup$ I'm using Python 3.8. What's your suggestion? $\endgroup$
    – cammil
    Commented Mar 12, 2020 at 10:57
  • 1
    $\begingroup$ What’s “O(1) relative to N”? $\endgroup$
    – gnasher729
    Commented Mar 12, 2020 at 17:09
  • 1
    $\begingroup$ A format-preserving encryption function is an invertible mapping from $\{1,\ldots,N\}$ to $\{1,\ldots,N\}$, also known as a permutation. In order to generate $m$ random integers without replacement, choose a random key, and apply your FPE to $1,\ldots,m$. Unfortunately I have never heard of libffx, so can't help you with that. $\endgroup$ Commented May 15, 2020 at 9:38


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.