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. ArnaultT. 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. ArnaultT. 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

Figure 1.  An algebraic feedback shift register of Length m
Figure 2.  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]

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

[10]

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

[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]

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

[13]

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

[14]

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

[15]

Brigitte Vallée. Euclidean dynamics. Discrete & Continuous Dynamical Systems - A, 2006, 15 (1) : 281-352. doi: 10.3934/dcds.2006.15.281

[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

Metrics

  • PDF downloads (9)
  • HTML views (4)
  • Cited by (0)

Other articles
by authors

[Back to Top]