An algorithm which efficiently generates random samples without replacement, from a large range [0-N], N ~ 10^12?

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.

• Use a block cipher. Specifically, Format-preserving encryption. Mar 11, 2020 at 21:24
• 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? Mar 12, 2020 at 1:59
• I'm using Python 3.8. What's your suggestion? Mar 12, 2020 at 10:57
• What’s “O(1) relative to N”? Mar 12, 2020 at 17:09
• 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. May 15, 2020 at 9:38