The ISO random number generation standard, ISO 28640, speaks of a “Pentanomial GFSR method” for generating random variates. What is this? We’ll break it down, starting with GFSR.
GFSR
In short, a GFSR random number generator is what is now more commonly called a linear feedback shift register, or LFSR. The terminology “GFSR” was already dated when the ISO standard was published in 2010.
Tausworthe [1] came up with LFSR random variate generators in 1965. His paper looked at linear feedback shift registers but doesn’t use the term LFSR. LFSRs are bit sequences in which the current bit is a linear combination of certain previous bits, something like a Fibonacci sequence. The algebra is being carried out mod 2, so addition amounts to XOR.
As a toy example, consider
xn+5 = xn+2 + xn.
The first five bits would be the seed for the generator, then the recurrence above determines the rest. So, for example, we might start with 01101. Then the sequence of bits would be
011011101010000100101100111110001101110101…
It seems the term GFSR dates to 1973 with Lewis and Payne [2]. As far as I can tell, between 1965 and 1973 Tausworthe’s idea was implemented in practice using two previous terms, and this specialization of LFSRs became known as FSRs. Then [2] generalized this to include possibly more previous terms, restoring the generality of [1].
That explains “GFSR method” but what is this “pentanomial”?
Pentanomial
Recurrence relations can be described in terms of their characteristic polynomials. For example, in the familiar Fibonacci sequence
Fn+2 = Fn+1 + Fn
the characteristic polynomial is
x² – x – 1.
The characteristic polynomial of the toy generator above would be
x5 – x2 – 1.
And since -1 is the same as 1 when working mod 2, we’d usually write this polynomial as
x5 + x2 + 1.
Between 1965 and 1973 FSRs were implemented by terms that had a trinomial as the characteristic polynomial. Lewis and Payne looked at recurrences that depended on more previous terms, and in particular the choice of 4 previous terms, corresponding to a polynomial with 5 non-zero coefficients, had nice properties, hence the term “pentanomial.”
Primitive polynomials
The polynomials come before the recurrences. That is, we don’t write down the polynomial after designing the recurrence; the recurrence is designed by picking characteristic polynomials with special algebraic properties. This is because a primitive polynomial corresponds to the longest possible sequence of bits before things repeat.
The period of a LFSR corresponding to an nth degree primitive polynomial is 2n-1. This is the maximum possible because we cannot seed an LFSR with all zeros. We could, but the sequence would only produce zeros. As long as at least one bit in the seed is set, the LFSR will produce a sequence of 2n-1 bits before repeating.
Practicalities
In practice LFSRs are based on higher-degree polynomials than our toy example. For example, one might use
xn+607 = xn + xn+167 + xn+307 + xn+461
after seeding it with 607 random bits. This corresponds to the primitive pentanomial
x607 + x461 + x307 + x167 + 1.
This LFSR would have period 2607 – 1, or on the order of 10183 bits.
LFSRs are very fast, but they’re unsuitable for cryptography because linear feedback is linear and cryptanalysis can exploit linear structure. So in order to use LFSRs as secure random number generators they have to be combined with some sort of nonlinear processing, such as described here.
Related links
[1] Robert C. Tausworthe. Random Numbers Generated by Linear Recurrence Modulo Two. Mathematics of Computation, 19. 1965 pp. 201–209.
[2] T. G. Lewis and W. H. Payne. Generalized Feedback Shift Register Pseudorandom Number Algorithm. Journal of the ACM. Vol 20, No. 3. July 1973. pp. 456–468