Primitive polynomials, Singer cycles and word-oriented linear feedback shift registers

DOI10.1007/S10623-010-9387-7MaRDI QIDQ629934zbMATH OpenOpenAlexFDO

Authors Sudhir R. Ghorpade, Sartaj Ul Hasan, Meena Kumari

Publication date 10 March 2011

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0904.1331

zbMATH Keywords

primitive polynomiallinear feedback shift register (LFSR)Singer cycleprimitive recursive vector sequenceSinger subgroupsplitting subspaces

Mathematics Subject Classification ID

Cryptography (94A60) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Polynomials over finite fields (11T06) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Linear algebraic groups over finite fields (20G40)

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 $sigma$-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.

Recommendations

• Word-oriented transformation shift registers and their linear complexity
• The cycle structure of LFSR with arbitrary characteristic polynomial over finite fields
• Word-oriented linear feedback shift registers: \(\sigma\)-LFSRs
• A note on cyclotomic polynomials and Linear Feedback Shift Registers
• Block companion singer cycles, primitive recursive vector sequences, and coprime polynomial pairs over finite fields

Cites work

• scientific article; zbMATH DE number 3882549 (Why is no real title available?)
• scientific article; zbMATH DE number 3887879 (Why is no real title available?)
• scientific article; zbMATH DE number 3785000 (Why is no real title available?)
• scientific article; zbMATH DE number 3422259 (Why is no real title available?)
• A Theorem in Finite Projective Geometry and Some Applications to Number Theory
• Block companion singer cycles, primitive recursive vector sequences, and coprime polynomial pairs over finite fields
• Counting nilpotent endomorphisms
• Endliche Gruppen I
• Factorization of polynomials and some linear-algebra problems over finite fields
• Improved bounds in the multiple-recursive matrix method for pseudorandom number and vector generation
• On the number of matrices with given characteristic polynomial
• On the number of nilpotent matrices with coefficients in a finite field
• Order of elements in the groups related to the general linear group.
• Pseudorandom Vector Generation by the Multiple-Recursive Matrix Method
• Remarks on Singer cyclic groups and their normalizers.
• The multiple-recursive matrix method for pseudorandom number generation
• The probability that a matrix be nilpotent

Cited in

(29)

• Word-oriented transformation shift registers and their linear complexity
• A note on the multiple-recursive matrix method for generating pseudorandom vectors
• Methods of construction of skew linear recurrent sequences with maximal period based on the Galois polynomials factorization in the ring of matrix polynomials
• Enumeration of linear transformation shift registers
• The splitting subspace conjecture
• Investigating results and performance of search and construction algorithms for word-based LFSRs, \(\sigma\)-LFSRs
• Representations of skew linear recurrent sequences of maximal period over finite field;Представления скрученных линейных рекуррентных последовательностей максимального периода над конечным полем
• Description of maximal skew linear recurrences in terms of multipliers
• New representaions of elements of skew linear recurrent sequences via trace function based on the noncommutative Hamilton-Cayley theorem
• A construction of skew LRS of maximal period over finite fields based on the defining tuples of factors
• Digit sequences of skew linear recurrences of maximal period over Galois rings
• Skew \(\sigma\)-splittable linear recurrent sequences with maximal period
• A triangular class of skew maximum-period polynomials
• Primitive transformation shift registers over finite fields
• A note on cyclotomic polynomials and Linear Feedback Shift Registers
• Nonlinear vectorial primitive recursive sequences
• Skew LRS of maximal period over Galois rings
• The spectrality of self-affine measure under the similar transformation of \(GL_n(p)\)
• Unimodular polynomial matrices over finite fields
• Skew linear recurring sequences of maximal period over Galois rings
• An asymptotic formula for the number of irreducible transformation shift registers
• On the construction of irreducible and primitive polynomials from \(\mathbb{F}_{q^m} [x]\) to \(\mathbb{F}_q [x]\)
• New application methods for word-oriented cryptographic primitives
• The spectrality of a class of fractal measures on \(\mathbb{R}^n \)
• Block companion singer cycles, primitive recursive vector sequences, and coprime polynomial pairs over finite fields
• The cardinality of \(\mu_{M,D}\)-orthogonal exponentials for the planar four digits
• The cardinality of orthogonal exponentials of planar self-affine measures with three-element digit sets
• Enumeration of maximal cycles generated by orthogonal cellular automata
• On the number of irreducible linear transformation shift registers

This page was built for publication: Primitive polynomials, Singer cycles and word-oriented linear feedback shift registers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q629934)