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

DOI10.1007/S10623-010-9387-7zbMATH Open1263.11108arXiv0904.1331OpenAlexW3099877718MaRDI QIDQ629934FDOQ629934

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• A Theorem in Finite Projective Geometry and Some Applications to Number Theory
• Title not available (Why is that?)
• Endliche Gruppen I
• Title not available (Why is that?)
• Title not available (Why is that?)
• The probability that a matrix be nilpotent
• On the number of nilpotent matrices with coefficients in a finite field
• Counting nilpotent endomorphisms
• The multiple-recursive matrix method for pseudorandom number generation
• Block companion singer cycles, primitive recursive vector sequences, and coprime polynomial pairs over finite fields
• On the number of matrices with given characteristic polynomial
• Remarks on Singer cyclic groups and their normalizers.
• Order of elements in the groups related to the general linear group.
• 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
• Pseudorandom Vector Generation by the Multiple-Recursive Matrix Method

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
• On the construction of irreducible and primitive polynomials from \(\mathbb{F}_{q^m} [x]\) to \(\mathbb{F}_q [x]\)
• The spectrality of a class of fractal measures on \(\mathbb{R}^n \)
• An asymptotic formula for the number of irreducible transformation shift registers
• New application methods for word-oriented cryptographic primitives
• 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)