5

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

4
  • Once the period exceeds ~2^60 bytes it becomes completely meaningless. Mar 31, 2014 at 11:32
  • An ordinary random number generator only needs to produce statistically well-distributed numbers, but that doesn't mean they have to be hard-to-predict. In cryptography, we need hard-to-predict numbers in order to generate hard-to-guess keys. Mar 31, 2014 at 12:46
  • @CodesInChaos what makes you say that?
    – Celeritas
    Mar 31, 2014 at 17:21
  • 1
    If you have a PRNG which outputs 4 GB of random data (already pretty fast) per second, it will take 10 years to output 2^60 bytes. At 2^70 you're clearly in "you won't wait for that" territory. Mar 31, 2014 at 17:24

2 Answers 2

7

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:

  • We use a hash function h, with a n-bit output.
  • State S is a buffer of n bits.
  • To produce the next bit, we compute h(0||S) (hash of the concatenation of a bit of value 0, then S); the first bit of the output is the next bit; then we compute the new state S' = h(1||S).

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.

2
  • +1 for: 1. Such a great explaination 2. Clearing my concepts 3. "The important point here is that period is not a measure of security." :-) Mar 31, 2014 at 16:58
  • +1: But I would add the clarification that the the "period" measures the number of output bits (or "words", depending on terminology) after which the PRNG will certainly begin to repeat itself; it is a theoretical upper limit on the number of possible non-repeating outputs; in practice, it may be the case that no seed value actually attains the period; for the 4-digit Middle-Square algorithm the period is 8^4=4096 but the largest number of non-repeating outputs is 110; moreover, for the overwhelming majority of seed values, the "repetition" begins A LOT sooner than the period would suggest. Nov 27 at 15:55
3

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .