WANG Hui and FENG Xiutao, “The Adjacency Graphs of a Class of LFSRs and Their Applications,” Chinese Journal of Electronics, vol. 28, no. 6, pp. 1210-1216, 2019, doi: 10.1049/cje.2019.08.004
Citation: WANG Hui and FENG Xiutao, “The Adjacency Graphs of a Class of LFSRs and Their Applications,” Chinese Journal of Electronics, vol. 28, no. 6, pp. 1210-1216, 2019, doi: 10.1049/cje.2019.08.004

The Adjacency Graphs of a Class of LFSRs and Their Applications

doi: 10.1049/cje.2019.08.004
Funds:  This work is supported by the National Natural Science Foundation of China (No.61572491, No.11688101) and Science and Technology on Communication Security Laboratory (No.6142103010701).
More Information
  • Corresponding author: FENG Xiutao (corresponding author) was born in Hubei Province.He received the Ph.D.degree in computer software and theory from the University of Chinese Academy of Sciences.He is an associated professor of Academy of Mathematics and Systems Science,CAS.His research interests include cryptography and pseudorandom sequences.(Email:fengxt@amss.ac.cn)
  • Received Date: 2017-03-20
  • Rev Recd Date: 2017-10-12
  • Publish Date: 2019-11-10
  • Nonlinear feedback shift registers (NFSRs) are widely used in communication and cryptography. How to construct more NFSRs with maximal periods, which can generate sequences with maximal periods, i.e., de Brujin sequences, is an attractive problem. Recently many results on constructing de Bruijn sequences from adjacency graphs of Linear feedback shift registers (LFSRs) by means of the cycle joining method have been obtained. In this paper we discuss a class of LFSRs with characteristic polynomial p2(x), where p(x) is a primitive polynomial of degree n ≥ 2 over the finite field F2. As results, we determine their cycle structures and adjacency graphs, and further construct a class of new de Bruijn sequences from these LFSRs.
  • loading
  • S.W. Golomb, Shift Register Sequences, Holden-Day, San Francisco, USA, 1967.
    N. Zierler, "Linear recurring sequences", J. Soc. Indust. Appl. Math., Vol.7, No.1, pp.31-48, 1959.
    W. Meier and O. Staffelbach, "Fast correlation attacks on certain stream ciphers", J. Crypt., Vol.1, No.3, pp.159-176, 1989.
    A. Canteaut and M. Trabbia, "Improved fast correlation attacks using parity-check equations of weight 4 and 5", EUROCRYPT 2000, pp.573-588, 2000.
    N. Courtois and W. Meier, "Algebraic attacks on stream ciphers with linear feedback", LNCS, Vol.2656, pp.345-359, 2003.
    N. Courtois, "Fast algebraic attacks on stream ciphers with linear feedback", LNCS, Vol.2729, pp.176-194, 2003.
    H. Fredricksen, "A survey of full length nonlinear shift register cycle algorithms", SIAM Rev., Vol.24, No.2, pp.195-221, 1982.
    N.G. de Bruijn, "A combinatorial problem", Proc. Kon. Ned. Akad. Wetensch, Vol.49, pp.758-764, 1946.
    A. Lempel, "On a homomorphism of the de Bruijn graph and its applications to the design of feedback shift registers", IEEE Trans. Computers, Vol.19, No.12, pp.1204-1209, 1970.
    E.R. Hauge and J. Mykkeltveit, "On the classification of de Bruijn sequences", Discrete Math., Vol.148, No.1, pp.65-83, 1996.
    H. Fredricksen, "A class of nonlinear de Bruijn cycles", J. Combinat. Theory Ser. A, Vol.19, No.2, pp.192-199, 1975.
    T. Etzion and A. Lempel, "Algorithms for the generation of full-length shift-register sequences", IEEE Trans. Inf. Theory, Vol.30, No.3, pp.480-484, 1984.
    J. Mykkeltveit, M.K. Siu and P. Tong, "On the cycle structure of some nonlinear shift register sequences", Inf. Contr., Vol.43, No.2, pp.202-215, 1979.
    C. Li, X. Zeng, T. Helleseth, et al., "The properties of a class of linear FSRs and their applications to the construction of nonlinear FSRs", IEEE Trans. Inf. Theory, Vol.60, No.5, pp.3052-3061, 2014.
    C. Li, X. Zeng, C. Li, et al., "A class of de Bruijn sequences", IEEE Trans. Inf. Theory, Vol.60, No.12, pp.7955-7969, 2014.
    C. Li, X. Zeng, C. Li, et al., "Construction of de Bruijn sequences from LFSRs with reducible characteristic polynomial", IEEE Trans. Inf. Theory, Vol.62, No.1, pp.610-624, 2016.
    M. Li, D. Lin, "The adjacency graphs of linear feedback shift registers with primitive-like characteristic polynomial", https://eprint.iacr.org/2016/269,2016-3-10.
    E. Dubrova, "A scalable method for constructing Galois NLFSRs with period 2n-1 using cross-join pairs", IEEE Trans. Inf. Theory, Vol.59, No.1, pp.703-709, 2013.
    A. Salagean, "An algorithm for computing minimal bidirectional linear recurrence relations", IEEE Trans. Inf. Theory, Vol.55, No.10, pp.4695-4700, 2009.
    T. Helleseth, T. Kløve, "The number of cross-join pairs in maximum length linear sequences", IEEE Trans. Inf. Theory, Vol.37, No.6, pp.1731-1733, 1991.
    Z. Wan, Z. Dai, M. Liu, et al., Nonlinear Feedback Shift Registers, Chinese Science Press, 1978. (in Chinese)
    E.R. Hauge and T. Helleseth, "De Bruijn sequences, irreducible codes, and cyclotomy", Discrete Math., Vol.159, No.1, pp.143-154, 1996.
    S.W. Golomb and G. Gong, Signal Design for Good Correlation:For Wireless Communication, Cryptography, and Radar, Cambridge University Press, New York, USA, 2005.
    R. Lidl, H. Niederreiter, Finite Fields, Addison Wesley, MA, USA, 1983.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (282) PDF downloads(128) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return