# American Institute of Mathematical Sciences

February  2017, 11(1): 139-150. doi: 10.3934/amc.2017008

## AFSRs synthesis with the extended Euclidean rational approximation algorithm

 1 Department of Computer Science, William Paterson University of New Jersey, Wayne, NJ 07470 USA 2 Department of Computer Science, University of Kentucky, Lexington, KY 40506, USA

Received  July 2015 Published  February 2017

Fund Project: This material is based upon work supported by the National Science Foundation under grants No. CCF-0514660 and CNS-1420227. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.

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}$.

Citation: Weihua Liu, Andrew Klapper. AFSRs synthesis with the extended Euclidean rational approximation algorithm. Advances in Mathematics of Communications, 2017, 11 (1) : 139-150. doi: 10.3934/amc.2017008
##### References:

show all references

##### References:
An algebraic feedback shift register of Length m
The Extended Euclidean Rational Approximation Algorithm
 [1] Alexander Zeh, Antonia Wachter. Fast multi-sequence shift-register synthesis with the Euclidean algorithm. Advances in Mathematics of Communications, 2011, 5 (4) : 667-680. doi: 10.3934/amc.2011.5.667 [2] Ravi Anand, Dibyendu Roy, Santanu Sarkar. Some results on lightweight stream ciphers Fountain v1 & Lizard. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020128 [3] Claude Carlet, Khoongming Khoo, Chu-Wee Lim, Chuan-Wen Loe. On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity. Advances in Mathematics of Communications, 2008, 2 (2) : 201-221. doi: 10.3934/amc.2008.2.201 [4] A. Gasull, Víctor Mañosa, Xavier Xarles. Rational periodic sequences for the Lyness recurrence. Discrete & Continuous Dynamical Systems, 2012, 32 (2) : 587-604. doi: 10.3934/dcds.2012.32.587 [5] Domingo Gomez-Perez, Ana-Isabel Gomez, Andrew Tirkel. Arrays composed from the extended rational cycle. Advances in Mathematics of Communications, 2017, 11 (2) : 313-327. doi: 10.3934/amc.2017024 [6] Hassan Emamirad, Arnaud Rougirel. A functional calculus approach for the rational approximation with nonuniform partitions. Discrete & Continuous Dynamical Systems, 2008, 22 (4) : 955-972. doi: 10.3934/dcds.2008.22.955 [7] Martin Hanke, William Rundell. On rational approximation methods for inverse source problems. Inverse Problems & Imaging, 2011, 5 (1) : 185-202. doi: 10.3934/ipi.2011.5.185 [8] Rich Stankewitz, Hiroki Sumi. Random backward iteration algorithm for Julia sets of rational semigroups. Discrete & Continuous Dynamical Systems, 2015, 35 (5) : 2165-2175. doi: 10.3934/dcds.2015.35.2165 [9] Mary Wilkerson. Thurston's algorithm and rational maps from quadratic polynomial matings. Discrete & Continuous Dynamical Systems - S, 2019, 12 (8) : 2403-2433. doi: 10.3934/dcdss.2019151 [10] Frank Neubrander, Koray Özer, Lee Windsperger. On subdiagonal rational Padé approximations and the Brenner-Thomée approximation theorem for operator semigroups. Discrete & Continuous Dynamical Systems - S, 2020, 13 (12) : 3565-3579. doi: 10.3934/dcdss.2020238 [11] Xinmin Xiang. The long-time behaviour for nonlinear Schrödinger equation and its rational pseudospectral approximation. Discrete & Continuous Dynamical Systems - B, 2005, 5 (2) : 469-488. doi: 10.3934/dcdsb.2005.5.469 [12] Steven Richardson, Song Wang. The viscosity approximation to the Hamilton-Jacobi-Bellman equation in optimal feedback control: Upper bounds for extended domains. Journal of Industrial & Management Optimization, 2010, 6 (1) : 161-175. doi: 10.3934/jimo.2010.6.161 [13] Kyung Jae Kim, Jin Soo Park, Bong Dae Choi. Admission control scheme of extended rtPS algorithm for VoIP service in IEEE 802.16e with adaptive modulation and coding. Journal of Industrial & Management Optimization, 2010, 6 (3) : 641-660. doi: 10.3934/jimo.2010.6.641 [14] Fan Yuan, Dachuan Xu, Donglei Du, Min Li. An exact algorithm for stable instances of the $k$-means problem with penalties in fixed-dimensional Euclidean space. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021122 [15] David Julitz. Numerical approximation of atmospheric-ocean models with subdivision algorithm. Discrete & Continuous Dynamical Systems, 2007, 18 (2&3) : 429-447. doi: 10.3934/dcds.2007.18.429 [16] Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial & Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651 [17] Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 [18] Brigitte Vallée. Euclidean dynamics. Discrete & Continuous Dynamical Systems, 2006, 15 (1) : 281-352. doi: 10.3934/dcds.2006.15.281 [19] Marco Calderini. A note on some algebraic trapdoors for block ciphers. Advances in Mathematics of Communications, 2018, 12 (3) : 515-524. doi: 10.3934/amc.2018030 [20] Riccardo Aragona, Alessio Meneghetti. Type-preserving matrices and security of block ciphers. Advances in Mathematics of Communications, 2019, 13 (2) : 235-251. doi: 10.3934/amc.2019016

2020 Impact Factor: 0.935