Designing a New PRNG

> I don't disagree with anything specific that you said, but the reliance on "reasonable" means that you don't get a trivial guarantee about the lack of a short period from the structure itself.

I'm using "reasonable" here, because if the state-update function is an extremely weak and far-from-random permutation, like the identity, then the least-significant bits of the state will obviously display short cycles and, then, if your output function is also weak (e.g. simple truncation of most-significant bits), you may have short cycles in your output.

But, again, in such a case, you have a much bigger problem than "lack of lower bound on cycle length": your state-update function is not mixing your state, so you are 100% reliant on your output function to mix the state+counter. Also, if you go ahead and remove the counter, then you get a PRNG that always outputs the same thing (regardless of the chosen output function): clearly, you haven't picked a "reasonable" state-update function.

In a nutshell: if you don't actually have a PRNG (because both your state-update and output functions are trivially weak and non-mixing), then adding a counter won't magically turn it into a PRNG.

> The nice property that LFSR+non-linear-permutation-on-output schemes have is that by construction they give a guaranteed known gigantic period.

...and you get that guarantee from the fact that a LFSR is a counter. So you're just reinforcing what I said, and what is stated in the paper I linked to: adding a counter to a (stateful or stateless) nonlinear function is the best/easiest way to ensure a lower bound on the cycle length of a PRNG of arbitrary structure.

> If lots of cpu time is allowed then I think it's likely that people will manage to select reasonable permutations. ... but when trying to shave off ever last cycle (as is the case for the RNGs discussed in this thread) it would be good to have a more concrete definition of reasonable.

The chosen permutation does not have to have any special properties other than the ones that are already required for any usual PRNG (things like "changing a bit in the input should change each output bit with a probability of about 1/2").

The concrete definition of a "reasonable" PRNG is: either the state-update function or the output function of the PRNG must effectively mix the state (or both). Adding a counter will not turn an "unreasonable" PRNG into a "reasonable" PRNG: it will only take a "reasonable" PRNG and turn it into a "reasonable PRNG with lower bound on its cycle lengths".