Advanced Search
Article Contents
Article Contents

AFSRs synthesis with the extended Euclidean rational approximation algorithm

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 Full Text(HTML) Figure(2) Related Papers Cited by
  • 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}$.

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


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  An algebraic feedback shift register of Length m

    Figure 2.  The Extended Euclidean Rational Approximation Algorithm

  • [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.
    [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.
  • 加载中



Article Metrics

HTML views(432) PDF downloads(147) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint