A Lattice Rational Approximation Algorithm for AFSRs Over Quadratic Integer Rings

摘要

Algebraic feedback shift registers (AFSRs) are pseudorandom sequence generators that generalize linear feedback shift registers (LFSRs) and feedback with carry shift registers (FCSRs). With a general setting, AFSRs can result in sequences over an arbitrary finite field. It is well known that the sequences generated by LFSRs can be synthesized by either the Berlekamp-Massey algorithm or the extended Euclidean algorithm. There are three approaches to solving the synthesis problem for FCSRs, one based on the Euclidean algorithm, one based on the theory of approximation lattices and Xu's algorithm which is also used for some AFSRs. Xu's algorithm, an analog of the Berlekamp-Massey algorithm, was proposed by Xu and Klapper to solve the AFSR synthesis problem. In this paper we describe an approximation algorithm that solves the AFSR synthesis problem based on low-dimensional lattice basis reduction. It works for AFSRs over quadratic integer rings Z[D~(1/2)] with quadratic time complexity. Given the first 2φ_π(a) + c elements of a sequence a, it finds the smallest AFSR that generates a, where φ_π(a) is the π-adic complexity of a and c is a constant.