On the $ k $-error linear complexity of binary sequences of periods $ p^n $ from new cyclotomy

Vladimir Edemskiy; Chenhuang Wu; Vladimir Edemskiy; Chenhuang Wu

doi:10.3934/math.2022446

AIMS Mathematics

2022, Volume 7, Issue 5: 7997-8011. doi: 10.3934/math.2022446

Previous Article Next Article

Research article

On the $ k $-error linear complexity of binary sequences of periods $ p^n $ from new cyclotomy

Vladimir Edemskiy ¹,
Chenhuang Wu ^{2,3
,
,}

1.
Department of Applied Mathematics and Information Science, Yaroslav-the-Wise Novgorod State University, Veliky Novgorod, 173003, Russia
2.
Provincial Key Laboratory of Applied Mathematics, Putian University, Putian, Fujian 351100, China
3.
School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, Sichuan 611731, China

Received: 16 December 2021 Revised: 05 February 2022 Accepted: 10 February 2022 Published: 23 February 2022
MSC : 11B50, 94A55, 94A60

In this paper, we study the $ k $-error linear complexity of binary sequences with periods $ p^n $, which are derived from new generalized cyclotomic classes modulo a power of an odd prime $ p $. We establish a recursive relation and then estimate the $ k $-error linear complexity of the binary sequences with periods $ p^n $, the results extend the case $ p^2 $ that has been studied in an earlier work of Wu et al. at 2019. Our results show that the $ k $-error linear complexity of these sequences does not decrease dramatically for $ k < (p^{n}-p^{n-1})/2 $.
- $ k $-error linear complexity,
- binary sequences,
- cyclotomy,
- stream cipher,
- cryptography
Citation: Vladimir Edemskiy, Chenhuang Wu. On the $ k $-error linear complexity of binary sequences of periods $ p^n $ from new cyclotomy[J]. AIMS Mathematics, 2022, 7(5): 7997-8011. doi: 10.3934/math.2022446

Related Papers:

Abstract

In this paper, we study the $ k $-error linear complexity of binary sequences with periods $ p^n $, which are derived from new generalized cyclotomic classes modulo a power of an odd prime $ p $. We establish a recursive relation and then estimate the $ k $-error linear complexity of the binary sequences with periods $ p^n $, the results extend the case $ p^2 $ that has been studied in an earlier work of Wu et al. at 2019. Our results show that the $ k $-error linear complexity of these sequences does not decrease dramatically for $ k < (p^{n}-p^{n-1})/2 $.

References

[1]	T. W. Cusick, C. Ding, A. R. Renvall, Stream ciphers and number theory, Amsterdam: Elsevier, 2004.
[2]	C. S. Ding, T. Helleseth, New generalized cyclotomy and its applications, Finite Fields Appl., 4 (1998), 140–166. https://doi.org/10.1006/ffta.1998.0207 doi: 10.1006/ffta.1998.0207
[3]	Z. B. Xiao, X. Y. Zeng, C. L. Li, T. Helleseth, New generalized cyclotomic binary sequences of period $p^2$, Des. Codes Cryptogr., 86 (2018), 1483–1497. https://doi.org/10.1007/s10623-017-0408-7 doi: 10.1007/s10623-017-0408-7
[4]	Y. Ouyang, X. H. Xie, Linear complexity of generalized cyclotomic sequences of period $2p^m$, Des. Codes Cryptogr., 87 (2019), 2585–2596. https://doi.org/10.1007/s10623-019-00638-5 doi: 10.1007/s10623-019-00638-5
[5]	X. Y. Zeng, H. Cai, X. H. Tang, Y. Yang, Optimal frequency hopping sequences of odd length, IEEE T. Inform. Theory, 59 (2013), 3237–3248. https://doi.org/10.1109/TIT.2013.2237754 doi: 10.1109/TIT.2013.2237754
[6]	H. N. Liu, X. Liu, On the properties of generalized cyclotomic binary sequences of period $2p^m$, Des. Codes Cryptogr., 89 (2021), 1691–1712. https://doi.org/10.1007/s10623-021-00887-3 doi: 10.1007/s10623-021-00887-3
[7]	V. Edemskiy, C. L. Li, X. Y. Zeng, T. Helleseth, The linear complexity of generalized cyclotomic binary sequences of period $p^n$, Des. Codes Cryptogr., 87 (2019), 1183–1197. https://doi.org/10.1007/s10623-018-0513-2 doi: 10.1007/s10623-018-0513-2
[8]	Z. F. Ye, P. H. Ke, C. H. Wu, A further study of the linear complexity of new binary cyclotomic sequence of length $p^n$, AAECC, 30 (2019), 217–231. https://doi.org/10.1007/s00200-018-0368-9 doi: 10.1007/s00200-018-0368-9
[9]	S. Golomb, Shift register sequences, California: Aegean Park Press, 1967.
[10]	M. Stamp, C. F. Martin, An algorithm for the $k$-error linear complexity of binary sequences with period $2^n$, IEEE T. Inform. Theory, 39 (1993), 1398–1401. https://doi.org/10.1109/18.243455 doi: 10.1109/18.243455
[11]	C. H. Wu, C. X. Xu, Z. X. Chen, P. H. Ke, On error linear complexity of new generalized cyclotomic binary sequences of period $p^2$, Inform. Process. Lett., 144 (2019), 9–15. https://doi.org/10.1016/j.ipl.2018.08.006 doi: 10.1016/j.ipl.2018.08.006
[12]	Z. X. Chen, V. Edemskiy, P. H. Ke, C. H. Wu, On k-error linear complexity of pseudorandom binary sequences derived from Euler quotients, Adv. Math. Commun., 12 (2018), 805–816. https://doi.org/10.3934/amc.2018047 doi: 10.3934/amc.2018047
[13]	Z. X. Chen, Trace representations and linear complexity of binary sequences derived from Fermat quotients, Sci. China Inf. Sci., 57 (2014), 1–10. https://doi.org/10.1007/s11432-014-5092-x doi: 10.1007/s11432-014-5092-x
[14]	Z. X. Chen, X. N. Du, On the linear complexity of binary threshold sequences derived from Fermat quotients, Des. Codes Cryptogr., 67 (2013), 317–323. https://doi.org/10.1007/s10623-012-9608-3 doi: 10.1007/s10623-012-9608-3
[15]	Z. X. Chen, A. Ostafe, A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients, In: WAIFI 2010: Arithmetic of finite fields, Berlin, Heidelberg: Springer, 2010, 73–85. https://doi.org/10.1007/978-3-642-13797-6_6
[16]	Z. X. Chen, Z. H. Niu, C. H. Wu, On the k-error linear complexity of binary sequences derived from polynomial quotients, Sci. China Inf. Sci., 58 (2015), 1–15. https://doi.org/10.1007/s11432-014-5220-7 doi: 10.1007/s11432-014-5220-7
[17]	Z. Chen, X. Du, R. Marzouk, Trace representation of pseudorandom binary sequences derived from Euler quotients, AAECC, 26 (2015), 555–570. https://doi.org/10.1007/s00200-015-0265-4 doi: 10.1007/s00200-015-0265-4
[18]	Z. F. Ye, P. H. Ke, Z. X. Chen, Linear complexity of $d$-ary sequence derived from Euler quotients over $GF(q)$, Chinese J. Electron., 28 (2019), 529–534. https://doi.org/10.1049/cje.2019.02.004 doi: 10.1049/cje.2019.02.004
[19]	C. Zhao, W. P. Ma, T. J. Yan, Y. H. Sun, Linear complexity of least significant bit of polynomial quotients, Chinese J. Electron., 26 (2017), 573–578. https://doi.org/10.1049/cje.2016.10.008 doi: 10.1049/cje.2016.10.008
[20]	R. Lidl, H. Niederreiter, Finite fields, Cambridge: Cambridge University Press, 1997.
[21]	K. Ireland, M. Rosen, A classical introduction to modern number theory, New York: Springer, 1990.
[22]	V. Edemskiy, N. Sokolovskiy, The estimate of the linear complexity of generalized cyclotomic binary and quaternary sequences with periods $p^n$ and $2p^n$, Cryptogr. Commun., 2021. https://doi.org/10.1007/s12095-021-00534-7 doi: 10.1007/s12095-021-00534-7

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)