Enumeration of Linear Transformation Shift Registers

Abstract

We consider the problem of counting the number of linear transformation shift registers (TSRs) of a given order over a finite field. We derive explicit formulae for the number of irreducible TSRs of order two. An interesting connection between TSRs and self-reciprocal polynomials is outlined. We use this connection and our results on TSRs to deduce a theorem of Carlitz on the number of self-reciprocal irreducible monic polynomials of a given degree over a finite field.

16 pages

References in corpus (1)

• The Splitting Subspace Conjecture

Cited by in corpus (3)

• A note on the multiple-recursive matrix method for generating pseudorandom vectors
• An asymptotic formula for the number of irreducible transformation shift registers
• Primitive transformation shift registers over finite fields