Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.
Sign up to join this community
What is "period" in the context of pseudo-random number generators? For example when someone says "The Mersenne Twister has a 2^19337−1 period" what does it mean? I would appreciate a simple as possible explanation as possible.
What exactly is meant by "state" of a PRNG? On wikipedia I found "The sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's state, which includes a truly random seed."
As others have explained, the "period" measures the number of output bits (or "words", depending on terminology) after which the PRNG begins to repeat itself. For some PRNG this is relatively ill-defined. A PRNG is a deterministic algorithm with a state (the contents of its internal buffers and counters and variables). The sequence of subsequently emitted bits entirely depends on that state. If the PRNG uses a finite state (i.e. it fits in a fixed amount of RAM, without unbounded dynamic memory allocation) then it will mathematically begin repeat itself at some point, because there are only finitely many possible values for the complete state.
Not all PRNG are reversible. The PRNG is deterministic, meaning that from a given state value S, the next output bit and subsequent state S' can be unambiguously computed. A reversible PRNG is such that given state S, there is a unique previous state S'' for which S is the successor. LFSR are traditional reversible PRNG.
An example of non-reversible PRNG is the following hash-based PRNG:
Please note that this is just an example; I do not claim cryptographic security of that PRNG. Since there are only 2n possible values for S, we must necessarily encounter an already-seen state value after at most 2n+1 steps, so the "period" will be no more than 2n. However, the function which computes h(1||x) from x is not a permutation; it is expected to have collisions. This implies that when the PRNG "loops", it is rather improbable that it loops back to our initial state value. Instead, we expect (on average, depending on the hash function h) that such a PRNG will loop on a cycle of length about 2n/2; and we will reach that cycle after again an average 2n/2 steps. This implies that the first 2n/2 produced bits will (probably) not be repeated.
In that sense, the "period" does not measure all that is to be known about a PRNG. In fact, it is mostly impractical: in the hash-based example above, the "period" cannot be readily measured, and describes behaviour of the PRNG in conditions that will not actually be reachable in practice.
The important point here is that period is not a measure of security. Cryptographers do not care about the period. Period says anything about the security only in the special case that it is so short that it can be realistically explored. However, any period beyond 264 or so is "large enough" and becomes irrelevant.
In fact, if the description of a PRNG talks about the period, then it is a very definite indication that the PRNG was not designed or analysed by a cryptographer, and does not aim at cryptographic security (and usually won't provide it either). Indeed, the Mersenne Twister is meant for big physics simulation jobs, where there is no attacker to defeat except a mindless Nature. Cryptographers are more demanding, since they want to thwart an intelligent enemy who tries real hard to guess the next bits.
Every PRNG has an internal state which is used to compute the next output deterministically. The state is updated after each output. If the state has n bits after at least 2^n outputs the internal state must repeat which means that the PRNG produces the same sequence of outputs. Roughly speaking, the number of outputs until the internal state repeats is the period of a PRNG.
