Construction of Maximum Period Linear Feedback Shift Registers (LFSR) (Primitive Polynomials and Linear Recurring Relations)

Feedback Shift Register (FSR) is generally the basic element of pseudo random generators used to generate cryptographic channel or set of sequences for encryption keys. This type of generator is widely used in stream cipher and communication systems such as C.D.M.A (Code Division Multiple Access), mobile communication systems, ranging and navigating systems, spread spectrum communication systems.

The objective of the present paper is to propose a method for determining linear recurring sequences generating linear feedback shift register (LFSR) from primitive polynomials (and vice-versa). The linear recurring sequences facilitate the construction of maximum length LFSR. It also insists, in the last part, on the cryptographic security of LFSR and indicates some open problems in the area of nonlinear feedback shift registers (NLFSR) based pseudo random generators.