2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.