Volume 30 Issue 2
Apr.  2021
Turn off MathJax
Article Contents
LIU Junying, JIANG Yupeng, ZHENG Qunxiong, LIN Dongdai. Nonsingularity of Feedback Shift Registers of Degree at Most Three over a Finite Field[J]. Chinese Journal of Electronics, 2021, 30(2): 232-237. doi: 10.1049/cje.2021.01.009
Citation: LIU Junying, JIANG Yupeng, ZHENG Qunxiong, LIN Dongdai. Nonsingularity of Feedback Shift Registers of Degree at Most Three over a Finite Field[J]. Chinese Journal of Electronics, 2021, 30(2): 232-237. doi: 10.1049/cje.2021.01.009

Nonsingularity of Feedback Shift Registers of Degree at Most Three over a Finite Field

doi: 10.1049/cje.2021.01.009
Funds:

the National Natural Science Foundation of China 11701553

the National Natural Science Foundation of China 61872358

the National Natural Science Foundation of China 61872359

the National Postdoctoral Program for Innovative Talents BX201600188

the National Science Foundation for Post-doctoral Scientists of China 2017M611035

Young Elite Scientists Sponsorship Program by CAST 2016QNRC001

More Information
  • Author Bio:

    LIU Junying   was born in Shandong Province, China, in 1986. She received the Ph.D. degree in the State Key Laboratory of Information Security with Institute of Information Engineering of Chinese Academy of Sciences, Beijing, China. Her research interests include sequences and cryptography. (Email: jyliu6@163.com)

    JIANG Yupeng   received the Ph.D. degree in the Academy of Mathematics and Systems Science of Chinese Academy of Sciences, Beijing, China. His research interests include sequences and cryptography. (Email: jiangyupeng@iie.ac.cn)

    LIN Dongdai   received the Ph.D. degree in fundamental mathematics from the Institute of Systems Science, Chinese Academy of Sciences in 1990. He is currently a professor in the Institute of Information Engineering of Chinese Academy of Sciences and the director of the State Key Laboratory of Information Security. He is currently working on post quantum cryptography, sequences and stream cipher, Boolean functions. (Email: ddlin@iie.ac.cn)

  • Corresponding author: ZHENG Qunxiong  (corresponding author)  is currently a lecturer at PLA Strategic Support Force Information Engineering University, Zhengzhou, China. His main research interest is in stream cipher. (Email: qunxiong_zheng@163.com)
  • Received Date: 2019-09-25
  • Accepted Date: 2020-04-12
  • Publish Date: 2021-03-01
  • As a kind of generators of pseudorandom sequences, the Feedback shift register (FSR) is widely used in channel coding, cryptography and digital communication. A necessary and sufficient condition for the nonsingularity of a feedback shift register of degree at most three over a finite field is established. Using the above result, we can easily determine the nonsingularity of a feedback shift register from the algebraic normal form of the corresponding feedback function.
  • loading
  • [1]
    S. Golomb, Shift Register Sequences, Holden-Day, San Francisco, USA, pp. 115–117, 1967.
    [2]
    X.J. Lai, "Condition for the nonsingularity of a feedback shift register over a general finite field", IEEE Trans Inform Theory, Vol. 33, No. 50, pp. 747–757, 1987. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1057338
    [3]
    Z. Liu, Y. Wang and D. Cheng, "Nonsingularity of feedback shift registers", Automatica, Vol. 55, pp. 247–253, 2015. doi: 10.1016/j.automatica.2015.03.014
    [4]
    G.L. Mullen, "Permutation polynomials and nonsingular feedback shift registers over finite fields", IEEE Trans Inform Theory, Vol. 35, No. 4, pp. 900–902, 1989. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=32171
    [5]
    Y.X. Yang, "Nonsingular shift registers", Computer and Network, Vol. 17, No. 3, pp. 67–72, 1991. (in Chinese)
    [6]
    C. Li and D.Q. Xie, "Criterion for the nonsingularity of feedback shift registers", Joural of Electronics, Vol. 17, No. 5, pp. 500–505, 1995.
    [7]
    C. Li, "The numbering of nonsingular feedback function", Communication Security, Vol. 71, No. 3, pp. 68–71, 1997. http://en.cnki.com.cn/Article_en/CJFDTOTAL-TXBM199703012.htm
    [8]
    Q.Y. Wang and C.H. Jin, "Nonsingularity decision of Trivium-like cascade connection of feedback shift registers", Journal of Information Engineering University, Vol. 14, No. 5, pp. 519–523, 2013. http://en.cnki.com.cn/Article_en/CJFDTOTAL-XXGC201305002.htm
    [9]
    J.M. Zhang, W.F. Qi, T. Tian, et al., "Further results on the decomposition of an NFSR into the cascade connection of an NFSR into an LFSR", IEEE Trans Inform Theory, Vol. 61, No. 1, pp. 645–654, 2015. doi: 10.1109/TIT.2014.2371542
    [10]
    J.Q. Lu, M.L. Li, Y. Liu, et al., "Nonsingularity of Grain-like cascade FSRs via semi-tensor product", Sci China Inf Sci, Doi. org/10.1007/s11432-017-9269-6, 2018.
    [11]
    J.H. Zhong and D.D. Lin, "Decomposition of nonlinear feedback shift registers based on Boolean networks", Sci China Inf Sci, Doi. org/10.1007/s11432-017-9460-4, 2019.
    [12]
    R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, Reading, Boston, MA, USA, pp. 348–352, 1983.
    [13]
    C. Ma, W. Li, Z.B. Dai, et al., "A novel reconfigurable rotation-permutation unit research and implementation", Acta Electronica Sinica, Vol. 45, No. 5, pp. 1025–1034, 2017. (in Chinese) http://en.cnki.com.cn/Article_en/CJFDTotal-DZXU201705001.htm
    [14]
    B. Zhang, Y.L. Liu, X.J. Jing, et al., "Interweaving permutation meets block compressed sensing", Chinese Journal of Electronics, Vol. 27, No. 5, pp. 1056–1062, 2018. doi: 10.1049/cje.2017.04.001
    [15]
    C. Ronse, Feedback Shift Registers, Lecture Notes in Computer Sicence, Springer-Verlag, Berlin, Germany, 1984.
    [16]
    G. Myerson, "Period polynomials and Gauss sums for finite fields", Acta Arith, Vol. 39, pp. 251–264, 1981. doi: 10.4064/aa-39-3-251-264
  • 加载中

Catalog

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

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

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

    Figures(2)  / Tables(1)

    Article Metrics

    Article views (55) PDF downloads(18) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return