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$ Mar 11 '20 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
    Mar 12 '20 at 1:59
  • $\begingroup$ I'm using Python 3.8. What's your suggestion? $\endgroup$
    – cammil
    Mar 12 '20 at 10:57
  • 1
    $\begingroup$ What’s “O(1) relative to N”? $\endgroup$
    – gnasher729
    Mar 12 '20 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$ May 15 '20 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.