On lattice-based algebraic feedback shift registers synthesis for multisequences
type: Item
instance of: scholarly article
title: On lattice-based algebraic feedback shift registers synthesis for multisequences
zbMATH Open document ID: 1387.14077
author: L.-P. Wang
author: Daqing Wan
published in: Cryptography and Communications
publication date: 2018-02-19T00:00:00Z
review text: Synthesis problems for feedback shift registers (linear feedback shift registers (LFSR), feedback carry shift registers (FCSR) and algebraic feedback shift registers (AFSR)) aim to find a register, with the shortest length, which can produce a given recurrence sequence knowing only some of their initial terms. The Berlekamp-Massey algorithm is a well-known example of synthesis algorithm for LFSR over a finite field. AFSR were introduced by \textit{A. Klapper} and \textit{J. Xu} [Theor. Comput. Sci. 226, No. 1--2, 61--92 (1999; Zbl 0965.94014)] as a generalization of LFSR and FCSR. \textit{W. Liu} and \textit{A. Klapper} [Lect. Notes Comput. Sci. 8865, 200--211 (2014; Zbl 1345.94026)] proposed a synthesis algorithm for AFSR based on lattice theory. The present paper deals with AFSR synthesis problem for multisequences over three classes of (finite) quotient rings \(R/(\pi); \pi\in R\): \(\mathbb{Z}/(N)\)\, (that is FCSR), \(R\)\, some ramified extension of \(\mathbb{Z}\)\, and \(R\)\, a quadratic integer ring. The paper proves that, in the three cases, the synthesis problem can be reduced to the successive minima problem in a certain lattice. This allows to give an algorithm with polynomial complexity solving the synthesis problem. Section 2.1 outlines the AFSR synthesis problem for multisequences and Section 2.2 summarizes some basic facts about lattices, in particular the successive minima problem. The following Sections 3, 4 and 5 solve the synthesis problem over the three kind of rings quoted above.
Mathematics Subject Classification ID: 14G50
Mathematics Subject Classification ID: 11B37
Mathematics Subject Classification ID: 11J13
Mathematics Subject Classification ID: 94A55
zbMATH DE Number: 6840413
zbMATH Keywords: algebraic feedback shift registers
zbMATH Keywords: register synthesis problem
zbMATH Keywords: multisequences
zbMATH Keywords: lattices
zbMATH Keywords: successive minimal problem on lattices
reviewed by: Juan Tena Ayuso
MaRDI profile type: Publication
full work available at URL: s12095-017-0230-0
OpenAlex ID: W2618643689
cites work: A sieve algorithm for the shortest lattice vector problem
cites work: Feedback With Carry Shift Registers Synthesis With the Euclidean Algorithm
cites work: Some Sieving Algorithms for Lattice Problems
cites work: Q4856607
cites work: A uniform approach for Hermite Padé and simultaneous Padé approximants and their matrix-type generalizations
cites work: Fraction-free computation of simultaneous Padé approximants
cites work: Algebraic coding theory
cites work: Sampling methods for shortest vectors, closest vectors and successive minima
cites work: Q5611106
cites work: Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
cites work: Q3804606
cites work: A generalized Euclidean algorithm for multisequence shift-register synthesis
cites work: A generalization of the Berlekamp-Massey algorithm for multisequence shift-register synthesis with applications to decoding cyclic codes
cites work: Algebraic Shift Register Sequences
cites work: Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
cites work: Algorithms to construct Minkowski reduced and Hermite reduced lattice bases
cites work: On the Expected Value of the Joint 2-Adic Complexity of Periodic Binary Multisequences
cites work: Minkowski's Convex Body Theorem and Integer Programming
cites work: 2-Adic shift registers
cites work: Q4343440
cites work: Feedback shift registers, 2-adic span, and combiners with memory
cites work: Algebraic feedback shift registers
cites work: Register synthesis for algebraic feedback shift registers based on non-primes
cites work: Factoring polynomials with rational coefficients
cites work: A Lattice Rational Approximation Algorithm for AFSRs Over Quadratic Integer Rings
cites work: Shift-register synthesis and BCH decoding
cites work: On a class of arithmetic codes and a decoding algorithm (Corresp.)
cites work: Q3579369
cites work: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
cites work: Continued Fractions and Linear Recurrences
cites work: Algorithmic Number Theory
cites work: A method for solving key equation for decoding goppa codes
cites work: On the Lattice Basis Reduction Multisequence Synthesis Algorithm
cites work: On the joint 2-adic complexity of binary multisequences
DOI: 10.1007/S12095-017-0230-0
Recommended article: A Lattice Rational Approximation Algorithm for AFSRs Over Quadratic Integer Rings
Recommended article: \(F[x]\)-lattice basis reduction algorithm and multisequence synthesis
Recommended article: On the Lattice Basis Reduction Multisequence Synthesis Algorithm
Recommended article: Algebraic Feedback Shift Registers Based on Function Fields
Recommended article: Solving the FCSR synthesis problem for multi-sequences by lattice basis reduction
Recommended article: AFSRs synthesis with the extended Euclidean rational approximation algorithm
Recommended article: An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings
Recommended article: Register synthesis for algebraic feedback shift registers based on non-primes
Recommended article: Q3804606
description: scientific article; zbMATH DE number 6840413