AFSRs synthesis with the extended Euclidean rational approximation algorithm

Pseudo-random sequence generators are widely used in many areas, such as stream ciphers, radar systems, Monte-Carlo simulations and multiple access systems. Generalization of linear feedback shift registers (LFSRs) and feedback with carry shift registers (FCSRs), algebraic feedback shift registers (AFSRs) [ 7 ] can generate pseudo-random sequences over an arbitrary finite field. In this paper, we present an algorithm derived from the Extended Euclidean Algorithm that can efficiently find a smallest AFSR over a quadratic field for a given sequence. It is an analog of the Extended Euclidean Rational Approximation Algorithm [ 1 ] used in solving the FCSR synthesis problem. For a given sequence $\mathbf{a}$, $2\Lambda(\alpha)+1$ terms of sequence $\mathbf{a}$ are needed to find the smallest AFSR, where $\Lambda(\alpha)$ is a complexity measure that reflects the size of the smallest AFSR that outputs $\mathbf{a}$.