AFSRs synthesis with the extended Euclidean rational approximation algorithm

Weihua Liu; Andrew Klapper

doi:10.3934/amc.2017008

Article Contents

2017, Volume 11, Issue 1: 139-150. Doi: 10.3934/amc.2017008

This issue Previous Article On the multiple threshold decoding of LDPC codes over GF(q) Next Article Frequency hopping sequences with optimal aperiodic Hamming correlation by interleaving techniques

AFSRs synthesis with the extended Euclidean rational approximation algorithm

Weihua Liu^1, and
Andrew Klapper^2,

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: May 2017

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

Abstract / Introduction Full Text(HTML) Figure(2) Related Papers Cited by

Abstract

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

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Full Text(HTML)

Figure 1. An algebraic feedback shift register of Length m

Download: Full-size image PowerPoint slide

Figure 2. The Extended Euclidean Rational Approximation Algorithm

Download: Full-size image PowerPoint slide

Related Papers

Cited by

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.
[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.
[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.
[4]	M. Goresky and A. Klapper, Algebraic Shift Register Sequences, Cambridge Univ. Press, 2012.
[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.
[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.
[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.
[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.
[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.
[10]	W. LeVeque, Topics in Number Theory, Courier Corporation, 2002.
[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.
[12]	J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans. Inform. Theory, 15 (1969), 122-127.
[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.