On the Linear Complexity of a Class of Periodic Sequences Derived from Euler Quotients

LUO Bingyu; ZHANG Jingwei; ZHAO Chang’an

doi:10.23919/cje.2020.00.125

Volume 32 Issue 2

Mar. 2023

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2023 > 32(2): 262-272

LUO Bingyu, ZHANG Jingwei, ZHAO Chang’an. On the Linear Complexity of a Class of Periodic Sequences Derived from Euler Quotients[J]. Chinese Journal of Electronics, 2023, 32(2): 262-272. doi: 10.23919/cje.2020.00.125

Citation:

LUO Bingyu, ZHANG Jingwei, ZHAO Chang’an. On the Linear Complexity of a Class of Periodic Sequences Derived from Euler Quotients[J]. Chinese Journal of Electronics, 2023, 32(2): 262-272. doi: 10.23919/cje.2020.00.125

Citation:

PDF( 2934 KB)

On the Linear Complexity of a Class of Periodic Sequences Derived from Euler Quotients

doi: 10.23919/cje.2020.00.125

LUO Bingyu^1
,,
ZHANG Jingwei^2
,,
ZHAO Chang’an^{1, 3, 4
,}

1.
School of Mathematics, Sun Yat-sen University, Guangzhou 510275, China
2.
School of Information Science, Guangdong University of Finance and Economics, Guangzhou 510320, China
3.
Guangdong Key Laboratory of Information Security, Guangzhou 510006, China
4.
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China

Funds: This work was supported by Guangdong Major Project of Basic and Applied Basic Research (2019B030302008), the National Natural Science Foundation of China (61972428), the Open Fund of State Key Laboratory of Information Security (Institute of Information Engineering, Chinese Academy of Sciences) (2020-ZD-02), and Guangdong Basic and Applied Basic Research Foundation (2019A1515011797)

More Information

Author Bio:
Bingyu LUO received the B.E. degree in mathematics from Sun Yat-sen University. He is a Ph.D. candidate of Sun Yat-sen University. His research interests include sequences design and number theory. (Email: luoby@mail2.sysu.edu.cn)

Jingwei ZHANG received the Ph.D. degree in electronics engeneering from Sun Yat-sen University. She currently works in School of Information Science, Guangdong University of Finance and Economics in Guangdong. Her research interests include sequences design and coding theory. (Email: jingweizhang@gdufe.edu.cn)

Chang’an ZHAO (corresponding author) received the B.E. degree in electronical engineering in 2001, the M.E. degree in applied mathematics in 2005, the Ph.D. degree in information science and technology in 2008 respectively from Sun Yat-sen University, Guangzhou, China. He presently works in School of Mathmatics in Sun Yat-sen University. His research interest lies in elliptic curve cryptography, sequences designs, and coding theory. (Email: zhaochan3@mail.sysu.edu.cn)
Received Date: 2020-05-06
Accepted Date: 2021-08-21

Available Online: 2022-01-05

Publish Date: 2023-03-05

Abstract

Abstract

In this paper, a family of binary sequences derived from Euler quotients with RSA modulus pq is introduced. Here two primes p and q are distinct and satisfy gcd(pq, (p−1)(q−1))=1. The linear complexities and minimal polynomials of the proposed sequences are determined. Besides, this kind of sequences is shown not to have correlation of order four although there exist some special relations by the properties of Euler quotients.
- Cryptography,
- Binary sequences,
- Linear complexity,
- Euler quotients,
- RSA modulus

FullText(HTML)

References(26)

References

[1]	Z. Chen, A. Ostafe, and A. Winterhof, “Structure of pseudorandom numbers derived from Fermat quotients,” in Arithmetic of Finite Fields – WAIFI 2010, Lecture Notes in Computer Science (vol.6087), Springer, Berlin, Heidelberg, pp.73–85, 2010.
[2]	Z. Chen and X. Du, “On the linear complexity of binary threshold sequences derived from Fermat quotients,” Designs, Codes and Cryptography, vol.67, no.3, pp.317–323, 2013. doi: 10.1007/s10623-012-9608-3
[3]	Z. Chen, Z. Niu, and C. Wu, “On the $k$-error linear complexity of binary sequences derived from polynomial quotients,” Sci. China Inform. Sci., vol.58, no.9, pp.1–15, 2015.
[4]	Z. Chen and A. Winterhof, “Additive character sums of polynomial quotients,” Contemp Math., vol.579, pp.67–73, 2012.
[5]	Z. Chen, “Trace representation and linear complexity of binary sequences derived from Fermat quotients,” Sci. China Inform. Sci., vol.57, no.11, pp.1–10, 2014.
[6]	X. Du, C. Wu, and W. Wei, “An extension of binary threshold sequences from fermat quotients,” Adv. in Math. of Comm., vol.10, no.4, pp.743–752, 2016. doi: 10.3934/amc.2016038
[7]	C. e. Zhao, W. Ma, T. Yan, and Y. Sun, “Linear complexity of least significant bit of polynomial quotients,” Chinese Journal of Electronics, vol.26, no.3, pp.573–578, 2017.
[8]	T. Agoh, K. Dilcher, and L. Skula, “Fermat quotients for composite moduli,” Journal of Number Theory, vol.66, no.1, pp.29–50, 1997. doi: 10.1006/jnth.1997.2162
[9]	Z. X. Chen and A. Winterhof, “On the distribution of pseudorandom numbers and vectors derived from Euler-Fermat quotients,” International Journal of Number Theory, vol.8, pp.631–641, 2012.
[10]	Z. Chen, X. Du, and R. Marzouk, “Trace representation of pseudorandom binary sequences derived from Euler quotients,” Appli. Alg. Eng. Commun. Comp., vol.26, no.6, pp.555–570, 2015. doi: 10.1007/s00200-015-0265-4
[11]	Z. Niu, Z. Chen, and X. Du, “Linear complexity problems of level sequences of Euler quotients and their related binary sequences,” Sci. China Inform. Sci., vol.59, pp.1–12, 2016.
[12]	J. Zhang, S. Gao, and C.-A. Zhao, “Linear complexity of a family of binary pq²-periodic sequences from Euler quotients,” IEEE Trans. Inform. Theory, vol.66, no.9, pp.5774–5780, 2020. doi: 10.1109/TIT.2020.2979838
[13]	Z. Ye, P. Ke, and Z. Chen, “Linear complexity of $d$-ary sequence derived from Euler quotients over GF(q),” Chinese Journal of Electronics, vol.28, no.3, pp.529–534, 2019.
[14]	C. Ding, G. Xiao, and W. Shan, The Stability Theory of Stream Ciphers, Springer, Berlin-Verlag, 1991.
[15]	P. Fan and M. Darnell, Sequence Design for Communications Applications, Australia and New Zealand: Jacaranda Wiley Ltd, 1996.
[16]	S. W. Golomb and G. Gong, Signal Design for Good Correlation for Wireless Communication, Cryptography and Radar, Cambridge University Press, 2005.
[17]	W. Su, Y. Yang, Z. Zhou, and X. Tang, “New quaternary sequences of even length with optimal auto-correlation,” Sci. China Inform. Sci., vol.61, no.2, pp.1–13, 2018.
[18]	Y. Yang and X. Tang, “Generic construction of binary sequences of period 2n with optimal odd correlation magnitude based on quaternary sequences of odd period N,” IEEE Trans. Inform. Theory, vol.64, no.1, pp.384–392, 2018. doi: 10.1109/TIT.2017.2767076
[19]	X.-X. Zhao, T. Tian, and W.-F. Qi, “A ring-like cascade connection and a class of NFSRs with the same cycle structures,” Designs, Codes and Cryptography, vol.86, no.12, pp.2775–2790, 2018. doi: 10.1007/s10623-018-0473-6
[20]	Y. Jiang and D. Lin, “Lower and upper bounds on the density of irreducible NFSRs,” IEEE Trans. Inform. Theory, vol.64, no.5, pp.3944–3952, 2018. doi: 10.1109/TIT.2018.2796127
[21]	J. Zhang, T. Tian, W. Qi, and Q. Zheng, “A new method for finding affine sub-families of NFSR sequences,” IEEE Trans. Inform. Theory, vol.65, no.2, pp.1249–1257, 2019. doi: 10.1109/TIT.2018.2858769
[22]	Z. Chen, V. Edemskiy, P. Ke, and C. Wu, “On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients,” Advances in Mathematics of Communications, vol.12, no.4, pp.805–816, 2018. doi: 10.3934/amc.2018047
[23]	J. Massey, “Shift-register synthesis and BCH decoding,” IEEE Trans. Inform. Theory, vol.15, no.1, pp.122–127, 1969.
[24]	A. Michael, Algebra. Pearson Prentice Hall, 2011.
[25]	C. Ding and T. Helleseth, “New generalized cyclotomy and its applications,” Finite Fields and Their Applications, vol.4, no.2, pp.140–166, 1998. doi: 10.1006/ffta.1998.0207
[26]	R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, New York, NY, USA: Cambridge University Press, 1986.