On the symmetric 2-adic complexity of periodic binary sequences

Zibi Xiao; Xiangyong Zeng; Meijian Ke

doi:10.3934/amc.2022088

Article Contents

2024, Volume 18, Issue 5: 1303-1314. Doi: 10.3934/amc.2022088

This issue Previous Article Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms Next Article Two constructions for optimal Z-complementary sequence sets

On the symmetric 2-adic complexity of periodic binary sequences

1.
College of Science, Wuhan University of Science and Technology, Wuhan 430081, Hubei, China
2.
Faculty of Mathematics and Statistics, Hubei Key Laboratory of Applied Mathematics, Hubei University, Wuhan 430062, China

^*Corresponding author: Xiangyong Zeng
^*Corresponding author: Xiangyong Zeng

Received: May 1, 2022

Revised: September 1, 2022

Early access: November 14, 2022

Published online: November 14, 2022

The work of X. Zeng was supported by the National Nature Science Foundation of China (NSFC) under Grant 62072161. The work of Z. Xiao and M. Ke was supported by the National Natural Science Foundation of China (NSFC) under Grant 12061027.

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

Symmetric 2-adic complexity is a better measure for assessing the strength of a periodic binary sequence against the rational approximation attack. We study the symmetric 2-adic complexity of the sequences with known 2-adic complexity. To this end, we propose an equivalent definition of the symmetric 2-adic complexity and two sufficient conditions for a periodic sequence to achieve the maximum symmetric 2-adic complexity. As a first application, several types of sequences with maximum 2-adic complexity are easily shown to have the maximum symmetric 2-adic complexity. In addition, with the new definition, by analysing the algebraic structure of the sequences and applying the method for the calculation of their 2-adic complexity, we determine the symmetric 2-adic complexity of the Ding-Helleseth-Martinsen sequence and the sequence constructed by interleaving a pair of Legendre sequences.

Keywords:

Mathematics Subject Classification: Primary: 94A55, 94A60.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	Y. Cai and C. Ding, Binary sequences with optimal autocorrelation, Theoret. Comput. Sci., 410 (2009), 2316-2322. doi: 10.1016/j.tcs.2009.02.021.
[2]	T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, North-Holland Mathematical Library, 55. North-Holland Publishing Co., Amsterdam, 1998.
[3]	C. Ding, Autocorrelation values of generalized cyclotomic sequences of order two, IEEE Trans. Inf. Theory, 44 (1998), 1699-1702. doi: 10.1109/18.681354.
[4]	C. Ding and T. Helleseth, New generalized cyclotomy and its applications, Finite Fields Appl, 4 (1998), 140-166. doi: 10.1006/ffta.1998.0207.
[5]	C. Ding, T. Helleseth and K. Y. Lam, Several classes of sequences with three-level autocorrelation, IEEE Trans. Inf. Theory, 45 (1999), 2606-2612. doi: 10.1109/18.796414.
[6]	C. Ding, T. Helleseth and H. Martinsen, New families of binary sequences with optimal three-level autocorrelation, IEEE Trans. Inf. Theory, 47 (2001), 428-433. doi: 10.1109/18.904555.
[7]	V. Edemskiy and Y. Sun, The symmetric 2-adic complexity of sequences with optimal autocorrelation magnitude and length $8q$, Cryptogr. Commun., 14 (2022), 183-199. doi: 10.1007/s12095-021-00503-0.
[8]	V. Edemskiy and C. Wu, Symmetric 2-adic complexity of Ding-Helleseth generalized cyclotomic sequences of period $pq$, International Conference on Information Security and Cryptology, Guangzhou, China, 12612 (2021), 318-327.
[9]	S. Golomb and G. Gong, Signal Design for Good Correlation: For Wireless Communications, Cryptography and Radar Applications, Cambridge University Press, Cambridge, 2005. doi: 10.1017/CBO9780511546907.
[10]	G. Gong, Theory and applications of $q$-ary interleaved sequences, IEEE Trans. Inf. Theory, 41 (1995), 400-411. doi: 10.1109/18.370141.
[11]	R. Hofer and A. Winterhof, On the 2-adic complexity of two-prime generator, IEEE Trans. Inf. Theory, 64 (2018), 5957-5960. doi: 10.1109/TIT.2018.2811507.
[12]	H. Hu, Comments on a new method to compute the 2-adic complexity of binary sequences, IEEE Trans. Inf. Theory, 60 (2014), 5803-5804. doi: 10.1109/TIT.2014.2336843.
[13]	H. Hu and D. Feng, On the 2-adic complexity and k-error 2-adic complexity of periodic binary sequences, IEEE Trans. Inf. Theory, 54 (2008), 874-883. doi: 10.1109/TIT.2007.913238.
[14]	A. Klapper and M. Goresky, Cryptanalysis based on $2$-adic rational approximation, Advances in Cryptology-CRYPTO'95, Santa Barbara, California, USA, 963 (1995), 262-273. doi: 10.1007/3-540-44750-4_21.
[15]	A. Klapper and M. Goresky, Feedback shift registers, $2$-adic span, and combiners with memory, J. Cryptology, 10 (1997), 111-147. doi: 10.1007/s001459900024.
[16]	T. Storer, Cyclotomy and Difference Sets, Markham Publishing Co., Chicago, 1967.
[17]	Y. Sun, T. Yan, Z. Chen and L. Wang, The 2-adic complexity of a class of binary sequences with optimal autocorrelation magnitude, Cryptogr. Commun., 12 (2020), 675-683. doi: 10.1007/s12095-019-00411-4.
[18]	Y. Sun, T. Yan and Q. Wang, The 2-adic complexity of Yu-Gong sequences with interleaved structure and optimal autocorrelation magnitude, Des. Codes Cryptogr., 89 (2021), 695-707. doi: 10.1007/s10623-020-00841-9.
[19]	X. Tang and C. Ding, New classes of balanced quaternary and almost balanced binary sequences with optimal autocorrelation value, IEEE Trans. Inf. Theory, 56 (2010), 6398-6405. doi: 10.1109/TIT.2010.2081170.
[20]	X. Tang and G. Gong, New constructions of binary sequences with optimal autocorrelation value/magnitude, IEEE Trans. Inf. Theory, 56 (2010), 1278-1286. doi: 10.1109/TIT.2009.2039159.
[21]	A. L. Whiteman, A family of difference sets, Illionis J. Math., 6 (1962), 107-121.
[22]	Z. Xiao and X. Zeng, 2-Adic complexity of two constructions of binary sequences with period 4N and optimal autocorrelation magnitude, Cryptogr. Commun., 13 (2021), 865-885. doi: 10.1007/s12095-021-00498-8.
[23]	Z. Xiao, X. Zeng and Z. Sun, 2-Adic complexity of two classes of generalized cyclotomic binary sequences, Int. J. Found. Comput. Sci., 27 (2016), 879-893. doi: 10.1142/S0129054116500350.
[24]	H. Xiong, L. Qu and C. Li, A new method to compute the 2-adic complexity of binary sequences, IEEE Trans. Inf. Theory, 60 (2014), 2399-2406. doi: 10.1109/TIT.2014.2304451.
[25]	H. Xiong, L. Qu and C. Li, 2-Adic complexity of binary sequences with interleaved structure, Finite Fields Appl., 33 (2015), 14-28. doi: 10.1016/j.ffa.2014.09.009.
[26]	L. Zhang, J. Zhang, M. Yang and K. Feng, On the 2-adic complexity of the Ding-Helleseth-Martinsen binary sequences, IEEE Trans. Inf. Theory, 66 (2020), 4613-4620. doi: 10.1109/TIT.2020.2964171.
[27]	N. Zierler, Legendre sequences, Lexington: MIT Lincoln Laboratory, 1958.