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] 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 [2] Andreu Ferré Moragues. Properties of multicorrelation sequences and large returns under some ergodicity assumptions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020386 [3] Ying Lin, Qi Ye. Support vector machine classifiers by non-Euclidean margins. Mathematical Foundations of Computing, 2020, 3 (4) : 279-300. doi: 10.3934/mfc.2020018 [4] Bo Tan, Qinglong Zhou. Approximation properties of Lüroth expansions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020389 [5] Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 [6] Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296 [7] Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463 [8] Bilal Al Taki, Khawla Msheik, Jacques Sainte-Marie. On the rigid-lid approximation of shallow water Bingham. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 875-905. doi: 10.3934/dcdsb.2020146 [9] P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178 [10] Simone Fagioli, Emanuela Radici. Opinion formation systems via deterministic particles approximation. Kinetic & Related Models, 2021, 14 (1) : 45-76. doi: 10.3934/krm.2020048 [11] Manuel Friedrich, Martin Kružík, Jan Valdman. Numerical approximation of von Kármán viscoelastic plates. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 299-319. doi: 10.3934/dcdss.2020322 [12] Baoli Yin, Yang Liu, Hong Li, Zhimin Zhang. Approximation methods for the distributed order calculus using the convolution quadrature. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1447-1468. doi: 10.3934/dcdsb.2020168 [13] Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 [14] Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107 [15] Editorial Office. Retraction: Honggang Yu, An efficient face recognition algorithm using the improved convolutional neural network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 901-901. doi: 10.3934/dcdss.2019060 [16] Editorial Office. Retraction: Xiaohong Zhu, Zili Yang and Tabharit Zoubir, Research on the matching algorithm for heterologous image after deformation in the same scene. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1281-1281. doi: 10.3934/dcdss.2019088 [17] Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007 [18] Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122 [19] Pierluigi Colli, Gianni Gilardi, Jürgen Sprekels. Deep quench approximation and optimal control of general Cahn–Hilliard systems with fractional operators and double obstacle potentials. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 243-271. doi: 10.3934/dcdss.2020213 [20] Michiyuki Watanabe. Inverse $N$-body scattering with the time-dependent hartree-fock approximation. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021002

2019 Impact Factor: 0.734