The *linear complexity* (LC) of a sequence is the size in
bits of the shortest linear feedback shift register (LFSR) which
can produce that sequence. The measure therefore speaks to the
difficulty of generating -- and perhaps analyzing -- a particular
sequence.

Randomness can be seen as the size of the smallest program to
produce a given sequence. But linear complexity *is* the
size of a LFSR "processor" to produce a sequence, and there is
an algorithm (Berlekamp-Massey) to measure the LC. So the
resulting LC value might be used to measure one view of
randomness.

- 1969
*Application:*Massey presents*the*article linking the Berlekamp algorithm to LFSR reconstruction.

- 1971
*Theory:*Groth describes nonlinear SR generators with high complexity.

- 1976
- 1979
*Theory:*Welch and Scholtz an algorithm for developing rational approximations using continued fractions ends up virtually equivalent to Massey-Berlekamp.

- 1981
*Text:*Clark and Cain.

- 1982
*Theory:*Ferguson and Forcade construct "multidimensional" generalizations of the Euclidean algorithm.

- 1983
*Text:*Blahut.

- 1984
*Theory:*Mandelbaum develops an arithmetic analog to Berlekamp-Massey.*Theory:*Cheng, like Welch and Sholtz before, also reports a deep similarity between continued fractions and Berlekamp-Massey.

- 1985
*Theory:*Brynielsson how to calculate the linear complexity of a function in GF(2^{e}) (instead of GF(2)) to avoid trading off linear complexity for correlation immunity.*Tutorial:*Herlestam addresses linear complexity.

- 1987
*Theory:*Siegenthaler and Forre shows how to construct sequences of high complexity.*Theory:*Dornstetter shows that Berlekamp-Massey can be derived from a version of Euclid's algorithm.*Application:*Rueppel and Staffelbach show how to compute the linear complexity of a resulting sequence when the LC of each constituent sequence is known.*Theory:*Imamura and Yoshida present an alternate and perhaps easier derivation of Berlekamp-Massey.

- 1989
*Theory:*Chan and Games: Linear complexity is generally a measure of linear*span,*related to*quadratic*span, which can be unexpectedly very much smaller than the linear value.

- 1994
*Algorithm:*Fuster-Sabater and Caballero-Gil compute a lower bound to linear complexity for a given design, using binary string operations.*Theory:*Massey and Serconek address the opportunity to measure the linear complexity of nonlinearly-filtered LFSR sequences using the discrete Fourier transform (DFT).*Algorithm:*Fitzpatrick finds an algorithm similar to Berlekamp-Massey which appears more suitable for a parallel hardware implementation.

- 1995
*Algorithm:*Fleischmann presents a modified Berlekamp-Massey which extends the model sequence in both directions around any given data bit.

Massey, J. 1969. Shift-Register Synthesis and BCH Decoding.IEEE Transactions on Information Theory.IT-15(1): 122-127.

"*Abstract* -- It is shown in this paper that the
iterative algorithm introduced by Berlekamp for decoding BCH
codes actually provides a general solution to the problem of
synthesizing the shortest linear feedback shift register
capable of generating the prescribed finite sequence of digits."
"The equivalence of the decoding problem for BCH codes to a
shift-register synthesis problem is demonstrated . . . ."

Groth, E. 1971. Generation of Binary Sequences With Controllable Complexity.IEEE Transactions on Information Theory.IT-17: 288-296.

"*Abstract*--Complexity of a binary sequence is measured
by the amount of the sequence required to define the remainder.
It is shown that, while maximum length
(*L* = 2^{r} - 1) sequences from *r*-stage
linear feedback generators have minimum complexity, it is a simple
matter to use such sequences as bases for deriving other more
complex sequences of the same length."

"As a preliminary, it is important to recognize that any sequence can be generated by one or more linear generators." ". . . it is apparent that the adjectives, linear or nonlinear, applied frequently to sequences have no real meaning. Generators may be characterized as linear or nonlinear, but sequences may not."

Key, E. 1976. An Analysis of the Structure and Complexity of Nonlinear Binary Sequence Generators.IEEE Transactions on Information Theory.IT-22: 732-736.

"**Abstract**--A method of analysis is presented for the
class of binary sequence generators employing linear feedback
shift registers with nonlinear feed-forward operations. This
class is of special interest because the generators are capable
of producing very long 'unpredictable' sequences."

"This paper presents a method of analysis based on Galois field theory that enables one to predict the generator complexity resulting from nonlinear operations. Moreover the theory provides a conceptually simple basis for synthesizing devices with the desired characteristics, and is readily extendable to a larger class of more complex generators."

Gustavson, F. 1976. Analysis of the Berlekamp-Massey Linear Feedback Shift-Register Synthesis Algorithm.IBM Journal of Research and Development.20: 204-212.

"**Abstract:** An analysis of the Berlekamp-Massey Linear
Feedback Shift-Register (LFSR) Synthesis Algorithm . . . ."
". . . we present Massey's algorithm and indicate which steps
contribute to the computation cost. We then prove what the
minimum, average, and maximum computation costs are in terms of
the numbers of multiplications and additions."

Welch, L. and R. Sholtz. 1979. Continued Fractions and Berlekamp's Algorithm.IEEE Transactions on Information Theory.IT-25(1): 19-27.

"*Abstract* -- Theorems are presented concerning the
optimality of rational approximations using non-Archimedean
norms. The algorithm for developing the rational approximations
is based on continued fraction techniques and is virtually
equivalent to an algorithm employed by Berlekamp for decoding
BCH codes. Several variations of the continued fraction
technique and Berlekamp's algorithm are illustrated on a
common example.

Clark, G. and J. Cain. 1981.Error-Correction Coding for Digital Communications.Plenum Press.

Includes Berlekamp-Massey, and a lot more.

Ferguson, H and R. Forcade. 1982. Multidimensional Euclidean algorithms.Journal Fur Dir Reine Und Angewandte Mathematik.Walter de Gruyter & Co.

"**Introduction.** Given a pair (*x, y*) of positive
real numbers, then one iteration of the Euclidean algorithm
replaces the larger number by its least non-negative residue
modulo the smaller number. If the two numbers are linearly
dependent, the repetition of this process will eventually
terminate with a pair in which one of the elements is zero.
(If the original pair were integers, then the remaining non-zero
element is their greatest common divisor.)"

"Another property of the Euclidean algorithm, fundamental to the study of continued fractions, is that it produces increasingly good rational approximations to the original pair of real numbers."

"We will construct an iterative algorithm for *n*-tuples,
generalizing both the terminating and approximating features of
the Euclidean algorithm. Thus, if the original *n*-tuple
of elements are Z-linearly dependent, the algorithm will
necessarily terminate and discover the Z-relation among the elements
of the original *n*-tuple. If the original *n*-tuple
elements are not Z-linearly dependent, then the algorithm will
"absolutely approximate" by producing lattice points arbitrarily
close to the line generated by the original *n*-tuple."

"We emphasize that a major difficulty in the problem of
constructing a generalization of the Euclidean algorithm is to
give an *iterative* algorithm."

Blahut, R. 1983.Theory and Practice of Error Control Coding.Addison-Wesley.

Covers decoding BCH codes both with Berlekamp-Massey and Euclidean algorithms, plus much more.

Mandelbaum, D. 1984. An Approach to an Arithmetic Analog of Berlekamp's Algorithm.IEEE Transactions on Information Theory.IT-30(5): 758-762.

"In 1968 Berlekamp [1] introduced an iterative procedure to
determine a polynomial fraction *A(x) / B(x)*
in which the coefficients are members of a field that, when
divided, yields a given polynomial sequence *S(x)*
in which the coefficients are, of course, members of the same
field." "Massey gave another elegant proof of this procedure
in terms of shift-registers [2]. Similar results were then
obtained with the Euclidean algorithm and continued fractions
[3]-[6]. Since continued fractions can be utilized with both
polynomials and numbers from the real field, using an algorithm
similar to the Berlekamp algorithm with real binary numbers was
investigated."

"The class of arithmetic codes to which the proposed algorithm will apply is usually termed arithmetic residue codes and is a natural coding method for residue computers [12], which multiply and add quickly by using the Chinese remainder theorem." "These residue codes are the arithmetic analogs of the Reed-Solomon codes, which also can be decoded by the Euclidean algorithm or Berlekamp's algorithm."

Cheng, U. 1984. On the Continued Fraction and Berlekamp's Algorithm.IEEE Transactions on Information Theory.IT-30(3): 541-544.

"*Abstract* -- Continued fraction techniques are
equivalent to Berlekamp's algorithm."

"Implementation of Berlekamp's algorithm by continued fraction
technique was introduced by Reed *et. al.* [2]. In [3],
Welch and Scholtz studied the equivalence between continued
fraction and Berlekamp's algorithm. We will show that all
entities in Berlekamp's algorithm [1] can be related to those in
the continued fraction."

Brynielsson, L. 1985. On The Linear Complexity of Combined Shift Register Sequences.Advances in Cryptology -- EUROCRYPT '85.156-160. Springer-Verlag.

"Many proposed keystream generators consist of a number of binary maximum length shift registers combined by a nonlinear binary function. The registers guarantee a long period and the nonlinear function destroys the linearity i.e. it gives the output sequence a large linear complexity [1] (linear equivalent [2]). In order to avoid correlation attacks the function should also be correlation immune [3] i.e. the output sequence should be statistically independent of the various inputs. There is however a trade off between the linear complexity and the order of correlation immunity . . . . The reason for this is that in the binary field GF(2) there are too few functions."

"In the field GF(2^{e}) the situation is different.
For instance, the polynomial function
x+y+3xy+2(x^{2}y+xy^{2})+x^{2}y^{2}
in GF(4) is both nonlinear and correlation immune. In order to
validate such a function one must be able to calculate its linear
complexity. That is the purpose of this paper."

Herlestam, T. 1985. On Functions of Linear Shift Register Sequences.Advances in Cryptology -- EUROCRYPT '85.119-129. Springer-Verlag.

"**Abstract**. This paper is intended as an overview,
presenting several results on the linear complexity of sequences
obtained from functions applied to linear shift register
sequences."

"Two well-known models for shift registers are in use. The Fibonacci model consists of cascaded memory boxes. The contents of each box is multiplied by a feedback coefficient before being taken to a common summing device to produce the feedback element."

"In the Galois model, adders are inserted between the memory boxes, the system output is multiplied by the feedback coefficients . . . and the products are taken to the adders."

"In both cases, the same shift register recurrence is obtained."

"Three different methods for handling this recurrence are in use. The linear algebraic (matrix) method is the most commonly used (e.g., Golomb (1967)) . . . ."

"Rewriting the shift register recurrence . . . we can apply the classical technique as use by Selmer (1966) and Key (1976) among others."

"Finally, the generating function method, used by Zierler (1959), can be applied to the shift register recurrence.

Siegenthaler, T. and R. Forre. 1987. Generation of Binary Sequences with Controllable Complexity and Idealr-Tuple Distribution.Advances in Cryptology -- EUROCRYPT '87.15-23.

"**Abstract**. A key stream generator is analyzed which
consists of a single linear feedback shift register (LFSR) with a
primitive connection polynomial and a nonlinear feedforward logic."
". . . a simple condition imposed on these logics ensures an ideal
*r*-tuple distribution for these keystreams."

"Groth [2] proposed a layered structure
for the feedforward logic to control the linear complexity of the
generated keystream. This arrangement generates keystreams of
large linear complexities, however, the statistics of these
keystreams is hard to control. Rueppel suggested [3]
*[ the dissertation ]* a simply realisable and therefore
practically useful class of feedforward logics such that a lower
bound for the keystream's linear complexity is guaranteed."

"Our analysis is based on Brynielsson's
powerful Theorem 1 from which the linear complexity for every
polynomial *f* applied to a maximum length sequence can be
computed even if we use it only for a function . . . ."

Dornstetter, J. 1987. On the Equivalence Between Berlekamp's and Euclid's Algorithms.IEEE Transactions on Information Theory.IT-33(3): 428-431.

"*Abstract* -- It is shown that Berlekamp's iterative
algorithm can be derived from a normalized version of Euclid's
extended algorithm."

"The similarity between Berlekamp's iterative algorithm [1] and the extended Euclidean algorithm [7] has been previously noticed by several authors [3], [4]." "The original version of the iterative algorithm has been simplified by Massey [2]. We shall show in Section II that all partial results generated by this simplified version are in agreement (to a reciprocation and a normalization factor) with those given by Euclid's algorithm."

Rueppel, R. and O. Staffelbach. 1987. Products of Linear Recurring Sequences with Maximum Complexity.IEEE Transactions on Information Theory.IT-33(1): 124-131.

"*Abstract* -- Conditions are derived which guarantee that
products of linear recurring sequences attain maximum linear
complexity. It is shown that the product of any number of
maximum-LENGTH GF(*q*) sequences has maximum linear
complexity, provided only the degrees of the corresponding
minimal polynomials are distinct and greater than two."

"A common type of running-key generator employed in stream
cipher systems consists of *n* (mostly maximum-length)
linear feedback shift registers (LFSR's) whose output sequences
are combined in a nonlinear function *F* to produce the
key stream." "One of the major objectives of *F* is to
increase the linear complexity of the key stream such that the
synthesis of a linear equivalent of the running-key generator
(e.g., by using the Berlekamp-Massey LFSR synthesis algorithm
[10]) becomes computationally feasible."

"We will stipulate that whenever we write of a product of two or more sequences we mean the termwise product of those sequences."

Imamura, K. and W. Yoshida. 1987. A Simple Derivation of the Berlekamp-Massey Algorithm and Some Applications.IEEE Transactions on Information Theory.IT-33(1): 146-150.

"The algorithm discovered by Berlekamp [1] for decoding BCH codes is very elegant. Massey [2] showed that Berlekamp's algorithm is best interpreted as an efficient recursive method for finding the shortest linear feedback shift register (LFSR) that generates a given sequence. Since Massey's interpretation is very useful, the algorithm is often called the Berlekamp-Massey algorithm."

"The derivation of the Berlekamp-Massey algorithm, however, seems to be rather difficult, and why it works is not so easy to understand [3], [4]." "The main purpose of this correspondence is to present a new method for deriving the Berlekamp-Massey algorithm . . . to make this important algorithm more easily understandable." "1) Find a general rule how the length of the LFSR grows with the sequence length and find a necessary and sufficient condition on the LFSR to be unique." "2) Find a recursive algorithm for updating the LFSR."

Chan, A. and R. Games. 1989. On the Quadratic Spans of Periodic Sequences.Advances in Cryptology -- CRYPTO '89.82-89. Springer-Verlag.

"The length of a shortest FSR [feedback shift register] that
generates the sequence is called the *span* of the sequence.

"Because of its tractability, most attention has been focused
on determining the *linear span* of a sequence -- the length
of the shortest linear FSR that generates the sequence."

"A sequence with very large linear span may be generated by a much shorter FSR if nonlinear terms are allowed in the feedback function."

Fuster-Sabater, A. and P. Caballero-Gil. 1994. On the Linear Complexity of Nonlinearly Filtered PN-sequences.Advances in Cryptology -- ASIACRYPT '94.80-90. Springer-Verlag.

"**Abstract**. A method of analysis for the linear complexity
of nonlinearly filtered PN-sequences is presented. The procedure
provides a general lower bound for the linear complexity and an
algorithm to improve it. The results obtained are valid for any
nonlinear function with a unique term of maximum order and for any
maximal-length LFSR. This work, which has as its starting point
'the root presence test' by Rueppel, is based on the handling of
binary strings instead of determinants in a finite field."

"Groth [1] presented the linear complexity as a controllable parameter with the order of F. Nevertheless, in his work there is no explicit mention to the degeneracies which may occur in the linear complexity of the produced sequence."

"Key [2] established the relationship between the minimal
polynomial roots required to represent the keystream generator
and the linear complexity of the generated sequence. This result
let Rueppel [7] state the so called *'root presence test'*
for the product of distinct phases of a PN-sequence."

". . . this paper proposes an algorithm to compute a lower bound for the complexity by using exclusively logic operations (OR, AND)."

Massey, J. and S. Serconek. 1994. A Fourier Transform Approach to the Linear Complexity of Nonlinearly Filtered Sequences.Advances in Cryptology -- CRYPTO '94.332-340. Springer-Verlag.

"By exploiting 'Blahut's theorem,' which states that the
linear complexity of an *N*-periodic sequence in
*GF(q) ^{N}* and the Hamming weight of its

Fitzpatrick, P. 1994. New time domain errors and erasures decoding algorithm for BCH codes.Electronics Letters.30(2): 110-111.

"A new algorithm is presented for solving the key equation that simultaneously computes the error locator polynomial and the errata evaluator polynomial. The algorithm is similar to the Berlekamp algorithm, but is more symmetrical in its treatment of the iterated pairs of polynomials making it particularly well suited to a highly parallel hardware implementation."

Fleischmann, M. 1995. Modified Berlekamp-Massey algorithm for two-sided shift-register synthesis.Electronics Letters.31(8): 605-606.

"*Introduction:* Massey introduced in [3] an algorithm for
calculating the shortest LFSR which generates a given finite
sequence . . . . In [3] the synthesizing process is one-sided
and a definite beginning or end of the sequence is needed.
However, some applications may be imagined where prior knowledge
of neither a sequence border nor the size of the sequence are
available. As a result, the algorithm has to start somewhere
within the sequence, and has to develop the LFSR using a two-sided
synthesising process."

*Last updated:* 1996-08-15