Primitive Polynomials, Singer Cycles, and Word-Oriented Linear Feedback Shift Registers
Primitive Polynomials, Singer Cycles, and Word-Oriented Linear Feedback Shift Registers
Sudhir R. Ghorpade
Department of Mathematics
Indian Institute of Technology Bombay,
Powai, Mumbai 400076, India
E-Mail: srg@math.iitb.ac.in
Sartaj Ul Hasan
Department of Mathematics
Indian Institute of Technology Bombay,
Powai, Mumbai 400076, India
and
Scientific Analysis Group
Defense Research and Development Organisation,
Metcalfe House, Delhi 110054, India
E-Mail: sartajulhasan@gmail.com
and
Meena Kumari
Scientific Analysis Group
Defense Research and Development Organisation,
Metcalfe House, Delhi 110054, India
E-Mail: rameena10@yahoo.co.in
Abstract
Using the structure of Singer cycles in general linear groups, we prove that a
conjecture of Zeng, Han and He (2007) holds in the affirmative in a special case, and
outline a plausible approach to prove it in the general case.
This conjecture is about the number of primitive σ-LFSRs of a given order
over a finite field, and it generalizes a known formula for the number of primitive LFSRs,
which, in turn, is the number of primitive polynomials of a given degree over a finite field.
Moreover, this conjecture is intimately related to an open question of Niederreiter (1995)
on the enumeration of splitting subspaces of a given dimension.
| 1 | Introduction | 1 |
| 2 | Primitive Polynomials and Primitive LFSRs | 3 |
| 3 | Singer Cycles and Singer Subgroups | 4 |
| 4 | Word-Oriented Feedback Shift Register: σ-LFSR | 5 |
| 5 | Block Companion Matrices | 6 |
| 6 | The Characteristic Map | 7 |
| 7 | The Case n = 1 | 9 |
| 8 | Examples | 10 |
| References | 11 |
This paper is published online in Designs, Codes and Cryptography, DOI: 10.1007/s10623-010-9387-7 (2010).
Download the full paper as:
Back to the List of Publications
Back to the Sudhir Ghorpade's Home Page