Efficient linear feedback shift registers with maximal period (Q1609404)

The paper suggests a solution to the problem posed in [\textit{B. Preneel} (ed.), Fast software encryption, 2nd international workshop, Leuven, Belgium 1994, Lect. Notes Comput. Sci. 1008 (1995; Zbl 0829.68005)] to design linear feedback shift registers that exploit the parallelism offered by the word oriented operations of modern processors. The idea lies in using a linear feedback shift register over the vector space \(F_2^m\) additionally equipped with a linear transformation \(T\). In some cases such a register, called linear tansformation shift register, can generate a sequence of vectors with very long period. The classical theory of binary linear feedback shift registers is extended to provide efficient algorithms for generation of irreducible and primitive linear transformation shift registers.