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

LIU Junying; JIANG Yupeng; ZHENG Qunxiong; LIN Dongdai

doi:10.1049/cje.2021.01.009

Volume 30 Issue 2

Apr. 2021

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2021 > 30(2): 232-237

LIU Junying, JIANG Yupeng, ZHENG Qunxiong, et al., “Nonsingularity of Feedback Shift Registers of Degree at Most Three over a Finite Field,” Chinese Journal of Electronics, vol. 30, no. 2, pp. 232-237, 2021, doi: 10.1049/cje.2021.01.009

Citation:

LIU Junying, JIANG Yupeng, ZHENG Qunxiong, et al., “Nonsingularity of Feedback Shift Registers of Degree at Most Three over a Finite Field,” Chinese Journal of Electronics, vol. 30, no. 2, pp. 232-237, 2021, doi: 10.1049/cje.2021.01.009

Citation:

PDF( 441 KB)

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

doi: 10.1049/cje.2021.01.009

LIU Junying^{1, 2
,},
JIANG Yupeng^2
,,
ZHENG Qunxiong^{2, 3, 4
,
,},
LIN Dongdai^2
,

1.
School of Mathematics and Statistics, Shandong University of Technology, Zibo 255091, China
2.
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
3.
State Key Laboratory of Cryptology, Beijing 100878, China
4.
PLA Strategic Support Force Information Engineering University, Zhengzhou 450002, China

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

Abstract

Abstract

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.
- Feedback shift register (FSR),
- Nonsingularity,
- Permutation polynomial,
- Cyclotomy,
- Quadratic form

FullText(HTML)

References(16)

References

[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