Historical Introduction

Summary

The prehistory of our subject can be backdated to 1202, with the appearance of Leonardo Pisano's Liber Abaci (Fibonacci 1202), containing the famous problem about breeding rabbits that leads to the linear recursion f_n+1 = f_n + f_n−1 for n ≥ 2, f₁ = f₂ = 1, which yields the Fibonacci sequence. Additional background can be attributed to Euler, Gauss, Kummer, and especially Edouard Lucas (Lucas 1876). For the history proper, the earliest milestones are papers by O. Ore (Ore 1934), R.E.A.C. Paley (Paley 1933), and J. Singer (Singer 1938). Ore started the systematic study of linear recursions over finite fields (including GF(2)), Paley inaugurated the search for constructions yielding Hadamard matrices, and Singer discovered the Singer difference sets that are mathematically equivalent to binary maximum length linear shift register sequences (also known as pseudorandom sequences, pseudonoise (PN) sequences, or m-sequences).

It appears that by the early 1950s devices that performed the modulo 2 sum of two positions on a binary delay line were being considered as key generators for stream ciphers in cryptographical applications. The question of what the periodicity of the resulting output sequence would be seemed initially mysterious. This question was explored outside the cryptographic community by researchers at a number of locations in the 1953–1956 time period, resulting in company reports by E. N. Gilbert at Bell Laboratories, by N. Zierler at Lincoln Laboratories, by L. R. Welch at the Jet Propulsion Laboratory, by S.W. Golomb at the Glenn L. Martin Company (now part of Lockheed-Martin), and probably by others as well.