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