Speaker: Sudhir R. Ghorpade
Abstract
Linear feedback shift registers, or in short LFSRs, are devices frequently used in cryptography and coding theory. In effect, a LFSR is a homogeneous linear recurrence relation with coefficients in a finite field. Of particular interest are the primitive LFSRs that give rise to infinite sequences with a maximum possible order of periodicity.
We will consider a seemingly recent generalization of classical LFSRs that was partly motivated by a problem of Preneel on designing fast and secure LFSRs with the help of the word operations of modern processors. We will be especially interested in a conjecture made 5 years ago by Zeng, Han and He (in the binary case) about the number of such word oriented LFSRs that are primitive.
We will discuss equivalent versions of this in terms of certain Singer cycles, i.e., elements of maximum order in general linear groups over a finite field. Further we will relate these to an open question of Niederrieter (1995) concerning the so called splitting subspaces over finite field. An outline the recent and not-so-recent progress on these questions that has eventually lead to the complete solution, will be presented.
We will also discuss some related questions and topics. Throughout, an attempt will be made to keep the prerequisites at a minimum.