[kittywav]

Just a small comment: you can do things to ensure that the period of a PRNG is longer than a certain lower bound for any input seed. For example, if you make the state-mixing function depend on a 64-bit counter, you'll ensure that the period is at least 2^64 (assuming the state-mixing function is reversible).

[nullc]

Assuming its a permutation and you output the whole thing.

However, you wouldn't output the whole thing (or you instantly leak the state), and I think in that case you don't get an automatic useful guarantee about the period anymore: For some seeds you could have the whole 0..2^64-1 counter span just output a few repeating values (or even a constant).

In that case the 'state' has a long period, true, but the output doesn't. If instead you use a construction where the output is guaranteed to have a known (large) period, you can follow that up with whatever permutation you want, but to preserve the period all of the permutation must be output.

[kittywav]

> Assuming its a permutation and you output the whole thing.

I'm assuming the state-mixing function is a permutation (i.e. the counter affects the whole state in a reversible way), but it is not required that the whole state is outputted.

> However, you wouldn't output the whole thing (or you instantly leak the state), and I think in that case you don't get an automatic useful guarantee about the period anymore: For some seeds you could have the whole 0..2^64-1 counter span just output a few repeating values (or even a constant).

The counter will always have the full period of 2^N (assuming N-bit counter), regardless of how it is initialized (i.e. regardless of seeding), as long as it is a simple "i = (i + 1) mod 2^N" counter.

What this does is to effectively change the (presumably fixed) state permutation function: instead of using a fixed one, you're applying a repeating sequence of 2^N slightly different state permutation functions, which ensures that the period of the state should be at least as large as that (and probably much larger).

Assuming the chosen state permutation function is reasonable (and does indeed mix the counter effectively), truncating the state to provide output should not lead to short cycles: if it does, then your permutation is probably not reasonable as primitive for a PRNG (i.e. you have worse problems in your generator than "small period").

For more information on the use of counters to ensure lower bounds on the periods of stream ciphers and PRNG, take a look at Rabbit [1] (or, in general, at the concept of "counter-assisted stream ciphers" [2]).

[1] https://www.ecrypt.eu.org/stream/rabbitpf.html

[2] https://arxiv.org/abs/cs/0112014v5

[nullc]

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.

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

The counter and truncated permutation will do so if the permutation is reasonable. 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.

[kittywav]

> 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".