patternMajor
Is there a PRNG that visits every number exactly once, in a non-trivial bitspace, without repetition, without large memory usage, before it cycles?
Viewed 0 times
prngoncewithoutnumbernonbitspaceeverytriviallargethat
Problem
PRNGs (pseudorandom number generators) generally have a bit length for the binary numbers they generate (e.g. 32 bits, 64 bits). This is the universe of their possible numbers.
It seems that they typically cycle when they reach their 2^bitlen number.
Is there one that, before it cycles, will generate each possible number in its universe, exactly once, without repetition, for larger bitspaces (e.g. 64, 128, 256), without large memory requirements (such as storing numbers generated so far, or a shuffled list of future numbers).
Another way to put this: Is there an algorithm than exhaustively “traverses” or “visits” each binary number in a bitspace, exactly once, in a pseudorandom order? (with large bitspace and low memory usage, as above)
EDITS:
I now have the impression that, while PRNGs do typically eventually cycle (repeat their sequence), the point at which one cycles is specific to the algorithm, and is usually NOT after 2^bitlen numbers (where bitlen is the size in bits of their binary output). Please correct this if wrong.
I expect that a PRNG is still a PRNG if it generates a duplicate number (within its period, before it cycles), or if it never generates (within its period) some numbers that are possible in the bitspace of its output. I'm not looking for these kinds.
I'm looking for an algorithm that works as if it's just reading off N-bit binary numbers from a massive randomly-shuffled list of all N-bit binary numbers, but without the massive memory requirement of such a list.
I'm interested in algorithms meeting this criteria that are pseudorandom in a cryptographically-secure way, and also those not cryptographically-secure that are quicker or simpler.
It seems that they typically cycle when they reach their 2^bitlen number.
Is there one that, before it cycles, will generate each possible number in its universe, exactly once, without repetition, for larger bitspaces (e.g. 64, 128, 256), without large memory requirements (such as storing numbers generated so far, or a shuffled list of future numbers).
Another way to put this: Is there an algorithm than exhaustively “traverses” or “visits” each binary number in a bitspace, exactly once, in a pseudorandom order? (with large bitspace and low memory usage, as above)
EDITS:
I now have the impression that, while PRNGs do typically eventually cycle (repeat their sequence), the point at which one cycles is specific to the algorithm, and is usually NOT after 2^bitlen numbers (where bitlen is the size in bits of their binary output). Please correct this if wrong.
I expect that a PRNG is still a PRNG if it generates a duplicate number (within its period, before it cycles), or if it never generates (within its period) some numbers that are possible in the bitspace of its output. I'm not looking for these kinds.
I'm looking for an algorithm that works as if it's just reading off N-bit binary numbers from a massive randomly-shuffled list of all N-bit binary numbers, but without the massive memory requirement of such a list.
I'm interested in algorithms meeting this criteria that are pseudorandom in a cryptographically-secure way, and also those not cryptographically-secure that are quicker or simpler.
Solution
Sure. Pick a block cipher (i.e., pseudorandom permutation), $E_K$, and a random key for it, $K$. Let $x_i=E_K(i)$. Then this has the properties you are looking for.
Short explanation:
As the block cipher $E_K$ maps each n-bit value uniquely to another n-bit value, all the resulting values must be different for different input values.
Effectively that means $E_K$ creates a permutation of n-bit values that can be varied by changing $K$.
Short explanation:
As the block cipher $E_K$ maps each n-bit value uniquely to another n-bit value, all the resulting values must be different for different input values.
Effectively that means $E_K$ creates a permutation of n-bit values that can be varied by changing $K$.
Context
StackExchange Computer Science Q#153104, answer score: 39
Revisions (0)
No revisions yet.