turkmath.org

We consider recursively generated infinite sequences of a given order with entries in a finite field. Classically, this is done using the so called LFSRs, that is, linear feedback shift registers, and it is known that primitive LFSRs give rise to sequences having the maximum period possible, which are useful in cryptology. About a decade ago, a generalization of LFSRs to what are known as sigma-LFSRs was proposed by Zeng, Han and He in the binary case, who posed a nice open problem about the number of primitive sigma-LFSRs of a given order. It turns out that these sigma-LFSRs were studied much earlier by Niederreiter who considered vector recurrences and proposed the so-called multiple recursive matrix method. In this connection, he had also proposed an open question about the so-called splitting subspaces. We will show further connections to Singer cycles, which arise in the theory of finite (general linear) groups, and outline an early progress on these open problems and a quantitative formulation of Niederreiter's question in the general q-ary case. In fact, these developments ultimately lead to a settlement of these questions. Along the way, we will consider the following question that is related and has been of some recent interest: what is the probability that two randomly chosen polynomials of positive degree with coefficients in a finite field are relatively prime?