Does the permutation cycle of a PRNG change completely with different seeds?

Question

Apologies if this seems like a trivial question.

I've been learning PRNG and cryptographic basics and I don't think I've found an answer to this question (At least that I understand).

My understanding is that a PRNG has an internal state which is seeded with another random number (or semi-random such as epoch time). This seed dictates what point the state starts in its permutation cycle which is defined as 2^n (n being the total bits of its state).

My question is that given given two instances of the same PRNG (such as MWC1616 or a LCG) with two different seeds, does their permutation cycle change so that one seed may never generate a number that would be contained in the cycle of the other instance or do they both exist within the same cycle just at a different point along it?

Answer 1

It is possible for two PRNG instances with different seeds to have overlapping cycles. The probability of this happening depends on factors like the PRNG algorithm(s), the seed space, and the specific seed values, whereby some PRNGs, especially those with short periods or poor design, are more likely to have overlapping cycles at all.

Take a look at the following answers as well:

• https://crypto.stackexchange.com/questions/54738/can-two-different-seeds-produce-the-same-output-from-a-prng
• https://stackoverflow.com/questions/12150354/can-two-prngs-produce-the-same-number-with-different-seeds

In this context: I think your question fits best into crypto.stackexchange.

Answer 2

It depends on the PRNG. If there are at least as many seeds as possible outputs, then by necessity each instance must at some point generate a number that at some is generated by another instance. But if the number of seeds is smaller than the than the number of possible outputs then it's possible that different instances will never generate the same numbers, but that doesn't have to be the case. But how it works more precisely differs between different PRNGs. I'm not sure how the two examples you gave work, so I'll instead give an example of common cryptographic PRNGs.

Take a PRNG based on a block cipher in CTR mode, maybe one with 128-bit block size. If we use the first 64 bits of the IV as our seed and the remaining 64 bits as our counter, then two different instances with different seeds will never generate a number generated by the other instance. This is because all different IVs give unique outputs and we have 2^64 seeds, each having 2^64 different outputs, and the number of possible outputs is 2^128.

If we instead have a PRNG based on a hash function in CTR mode, then we have a different situation as two different inputs are not guaranteed to yield different outputs in the same way as ciphers are (see the difference between PRPs and PRFs). Some hash functions allow for inputs of (near) unlimited size and an output of n bits. It is easy to see that an infinite number of seeds can't all map uniquely to a smaller number of outputs.

And even for hash functions with a fixed input size, there are usually no guarantees for what values a cycle will contain, unlike with a cipher. Cryptographic hash functions give outputs that are indistinguishable from random outputs, so for those hash functions there certainly exists different PRNG instances with different seeds that at some point generate the same number as another instance generated.