Updating the seed key of a PRNG while maintaining initial entropy?

Question

Consider a seed key ($n$-bit long) is completely random and entropy of random variable is $n$ and PRNG is using deterministic algorithm and that that deterministic algorithm does not add any entropy to the random variable. Moreover, the PRNG length is $2^n-1$. So, how can we update the seed key of that PRNG to avoid repetitive output while maintaining the same initial entropy of the seed key?

Answer 1

It's a matter of periods in the sequence of numbers generated by the PRNG. If the output of the PRNG has a single period that is of length $2^n$, then you can avoid repetition by appropriately recording the section that you have already used. Thus if you start from $0$ and get the first time to $g_1$, the next time you start from $g_1$ and get to $g_2$, etc. until you have used up the entire period (keep a count of the numbers generated in order to detect that). PRNGs that generate numbers in $[0, 2^{n-1}]$ may not necessarily have the maximal period length of $2^n$. One special kind of PRNGs that have the maximal period length are based on the so-called permutation polynomials mod $2^n$. I used it in one of my software (s13.zetaboards.com/Crypto/topic/7355166/1/), where a literature reference to permutation polynomials as well as a practical implementation of PRNGs based on them are given.