On lattice-based algebraic feedback shift registers synthesis for multisequences (Q1699261)

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.