# 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:
 [1] F. Arnault, T. P. Berger and A. Necer, Feedback with carry shift registers synthesis with the Euclidean algorithm, IEEE Trans. Inform. Theory, 50 (2004), 910-917. doi: 10.1109/TIT.2004.826651. Google Scholar [2] N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in Advances in Cryptology-EUROCRYPT 2003, Springer, 2003,345-359. doi: 10.1007/3-540-39200-9_21. Google Scholar [3] M. Goresky and A. Klapper, Feedback registers based on ramified extensions of the 2-adic numbers, in Advances in Cryptology-EUROCRYPT '94, Springer, 1995,215-222. doi: 10.1007/BFb0053437. Google Scholar [4] M. Goresky and A. Klapper, Algebraic Shift Register Sequences, Cambridge Univ. Press, 2012. Google Scholar [5] A. Klapper and M. Goresky, Cryptanalysis based on 2-adic rational approximation, in Advances in Cryptology-CRYPTO '95, Springer, 1995,262-273. doi: 10.1007/3-540-44750-4_21. Google Scholar [6] A. Klapper and M. Goresky, Feedback shift registers. 2-adic span, and combiners with memory, Cryptology J., 10 (1997), 111-147. doi: 10.1007/s001459900024. Google Scholar [7] A. Klapper and J. Xu, Algebraic feedback shift registers, Theoret. Comp. Sci., 226 (1999), 61-92. doi: 10.1016/S0304-3975(99)00066-3. Google Scholar [8] A. Klapper and J. Xu, Register synthesis for algebraic feedback shift registers based on nonprimes, Des. Codes Cryptogr., 31 (2004), 227-250. doi: 10.1023/B:DESI.0000015886.71135.e1. Google Scholar [9] D. Lee, J. Kim, J. Hong, J. Han and D. Moon, Algebraic attacks on summation generators, in Fast Software Encryption, Springer, 2004, 34-48. doi: 10.1007/978-3-540-25937-4_3. Google Scholar [10] W. LeVeque, Topics in Number Theory, Courier Corporation, 2002.Google Scholar [11] W. Liu and A. Klapper, A lattice rational approximation algorithm for AFSRs over quadratic integer rings, in Sequences and Their Applications -SETA 2014, Springer, 2014,200-211. doi: 10.1007/978-3-319-12325-7_17. Google Scholar [12] J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans. Inform. Theory, 15 (1969), 122-127. Google Scholar [13] P. Q. Nguyen and D. Stehlé, Low-dimensional lattice basis reduction revisited, ACM Trans. Algor. (TALG), 5 (2009), 46. doi: 10.1145/1597036.1597050. Google Scholar

show all references

##### References:
 [1] F. Arnault, T. P. Berger and A. Necer, Feedback with carry shift registers synthesis with the Euclidean algorithm, IEEE Trans. Inform. Theory, 50 (2004), 910-917. doi: 10.1109/TIT.2004.826651. Google Scholar [2] N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in Advances in Cryptology-EUROCRYPT 2003, Springer, 2003,345-359. doi: 10.1007/3-540-39200-9_21. Google Scholar [3] M. Goresky and A. Klapper, Feedback registers based on ramified extensions of the 2-adic numbers, in Advances in Cryptology-EUROCRYPT '94, Springer, 1995,215-222. doi: 10.1007/BFb0053437. Google Scholar [4] M. Goresky and A. Klapper, Algebraic Shift Register Sequences, Cambridge Univ. Press, 2012. Google Scholar [5] A. Klapper and M. Goresky, Cryptanalysis based on 2-adic rational approximation, in Advances in Cryptology-CRYPTO '95, Springer, 1995,262-273. doi: 10.1007/3-540-44750-4_21. Google Scholar [6] A. Klapper and M. Goresky, Feedback shift registers. 2-adic span, and combiners with memory, Cryptology J., 10 (1997), 111-147. doi: 10.1007/s001459900024. Google Scholar [7] A. Klapper and J. Xu, Algebraic feedback shift registers, Theoret. Comp. Sci., 226 (1999), 61-92. doi: 10.1016/S0304-3975(99)00066-3. Google Scholar [8] A. Klapper and J. Xu, Register synthesis for algebraic feedback shift registers based on nonprimes, Des. Codes Cryptogr., 31 (2004), 227-250. doi: 10.1023/B:DESI.0000015886.71135.e1. Google Scholar [9] D. Lee, J. Kim, J. Hong, J. Han and D. Moon, Algebraic attacks on summation generators, in Fast Software Encryption, Springer, 2004, 34-48. doi: 10.1007/978-3-540-25937-4_3. Google Scholar [10] W. LeVeque, Topics in Number Theory, Courier Corporation, 2002.Google Scholar [11] W. Liu and A. Klapper, A lattice rational approximation algorithm for AFSRs over quadratic integer rings, in Sequences and Their Applications -SETA 2014, Springer, 2014,200-211. doi: 10.1007/978-3-319-12325-7_17. Google Scholar [12] J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans. Inform. Theory, 15 (1969), 122-127. Google Scholar [13] P. Q. Nguyen and D. Stehlé, Low-dimensional lattice basis reduction revisited, ACM Trans. Algor. (TALG), 5 (2009), 46. doi: 10.1145/1597036.1597050. Google Scholar
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] A. Gasull, Víctor Mañosa, Xavier Xarles. Rational periodic sequences for the Lyness recurrence. Discrete & Continuous Dynamical Systems - A, 2012, 32 (2) : 587-604. doi: 10.3934/dcds.2012.32.587 [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] 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 [5] Hassan Emamirad, Arnaud Rougirel. A functional calculus approach for the rational approximation with nonuniform partitions. Discrete & Continuous Dynamical Systems - A, 2008, 22 (4) : 955-972. doi: 10.3934/dcds.2008.22.955 [6] 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 [7] Rich Stankewitz, Hiroki Sumi. Random backward iteration algorithm for Julia sets of rational semigroups. Discrete & Continuous Dynamical Systems - A, 2015, 35 (5) : 2165-2175. doi: 10.3934/dcds.2015.35.2165 [8] Mary Wilkerson. Thurston's algorithm and rational maps from quadratic polynomial matings. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 2403-2433. doi: 10.3934/dcdss.2019151 [9] 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 [10] 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 [11] 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 [12] Brigitte Vallée. Euclidean dynamics. Discrete & Continuous Dynamical Systems - A, 2006, 15 (1) : 281-352. doi: 10.3934/dcds.2006.15.281 [13] David Julitz. Numerical approximation of atmospheric-ocean models with subdivision algorithm. Discrete & Continuous Dynamical Systems - A, 2007, 18 (2&3) : 429-447. doi: 10.3934/dcds.2007.18.429 [14] 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 [15] 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 [16] 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 [17] 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 [18] Meng Yu, Jack Xin. Stochastic approximation and a nonlocally weighted soft-constrained recursive algorithm for blind separation of reverberant speech mixtures. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1753-1767. doi: 10.3934/dcds.2010.28.1753 [19] Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117 [20] Alessandro Gondolo, Fernando Guevara Vasquez. Characterization and synthesis of Rayleigh damped elastodynamic networks. Networks & Heterogeneous Media, 2014, 9 (2) : 299-314. doi: 10.3934/nhm.2014.9.299

2018 Impact Factor: 0.879