About symmetric 2-adic complexity of interleaving sequences based on Legendre sequences
https://doi.org/10.34680/2076-8052.2024.3(137).489-497
Abstract
2-adic complexity, along with linear complexity, are important characteristics of pseudorandom sequences that are significant for their practical applications. To assess the unpredictability of binary sequences, symmetric 2-adic complexity is preferred, which is defined as the lesser of the 2-adic complexity of the sequence and the 2-adic complexity of the sequence written in reverse order. The article studies the symmetric 2-adic complexity of alternating binary sequences with high linear complexity and good autocorrelation properties. To determine the sequences under consideration, cyclic shifts of Legendre sequences and their complements are used. It is shown that for these sequences the symmetric 2-adic complexity is close to the maximum possible and is sufficient to repel attacks using the rational approximation algorithm. The research method is based on the analysis of the relationship between the periodic autocorrelation function of a sequence, the values of which are known, and the generating polynomial of the sequence, inverse to the desired one.
About the Authors
V. A. Edemskiy
Yaroslav-the-Wise Novgorod State University
Russian Federation
Russian Federation
Veliky Novgorod
D. S. Droganova
Yaroslav-the-Wise Novgorod State University
Russian Federation
Russian Federation
Veliky Novgorod
References
1. Klapper A., Goresky M. Feedback shift registers, 2-adic span, and combiners with memory // Journal of Cryptology. 1997. 10 (2). 111-147. DOI: 10.1007/s001459900024
2. Goresky M., Klapper A. Algebraic Shift Register Sequences. Cambridge: Cambridge University Press, 2012.
3. Zhang L., Zhang J.,Yang M., Feng K. On the 2-adic complexity of the Ding- Helleseth-Martinsen binary sequences // IEEE Transactions on Information Theory. 2020. 66 (7). 4613-4620. DOI: 10.1109/TIT.2020.2964171
4. Sun F., Yue Q., Li X. On the 2-adic complexity of cyclotomic binary sequences of order four // Applicable Algebra in Engineering, Communication and Computing (AAECC), 2023. DOI: 10.1007/S00200-023-00598-3
5. Sun F., Yue Q., Li X. On the 2-adic complexity of cyclotomic binary sequences of order three // Advances in Mathematics of Communications. 2022. 16 (4). 985-999. DOI: 10.3934/amc.2022049
6. Xiao Z., Zeng X., Sun Z. 2-Adic complexity of two classes of generalized cyclotomic binary sequences // International Journal of Foundations Computer Science. 2016. 27 (7), 879-893. DOI: 10.1142/S0129054116500350
7. Hu H., Feng D. On the 2-adic complexity and the k-error 2-adic complexity of periodic binary sequences // IEEE Transactions on Information Theory. 2008. 54 (2). 874-883. DOI: 10.1109/TIT.2007.913238
8. Xiao Z., Zeng X., Ke M. On the symmetric 2-adic complexity of periodic binary sequences // Advances in Mathematics of Communications. 2024. 18 (5). 1303-1314. DOI: 10.3934/amc.2022088
9. Edemskiy V. Symmetric 4-adic complexity of quaternary sequences with low autocorrelation and period pq // Advances in Mathematics of Communications. 2024. 18 (6). 1723-1732. DOI: 10.3934/amc.2023017
10. Tang X., Gong G. New constructions of binary sequences with optimal autocorrelation value/magnitude // IEEE Transactions on Information Theory. 2010. 56 (3). 1278-1286. DOI: 10.1109/TIT.2009.2039159
11. Li N., Tang X. On the linear complexity of binary sequences of period 4N with optimal autocorrelation value/magnitude // IEEE Transactions on Information Theory. 2011. 57 (11). 7597-7604. DOI: 10.1109/TIT.2011.2159575
12. Xiong H., Qu L., Li C. 2-Adic complexity of binary sequences with interleaved structure // Finite Fields and their Applications. 2015. 33. 14-28. DOI: 10.1016/j.ffa.2014.09.009
13. Xiao Z., Zeng X. 2-Adic complexity of two constructions of binary sequences with period 4N and optimal autocorrelation magnitude // Cryptography and Communications. 2021. 13 (5). 865-885. DOI: 10.1007/s12095-021-00498-8
14. Wang Q., Du X. N. The linear complexity of binary sequences with optimal autocorrelation / IEEE Transactions on Information Theory. 2010. 56 (12). 6388-6397. DOI: 10.1109/TIT.2010.2079550
Review
For citations:
Edemskiy V.A., Droganova D.S. About symmetric 2-adic complexity of interleaving sequences based on Legendre sequences. Title in english. 2024;(3(137)):489-497. (In Russ.) https://doi.org/10.34680/2076-8052.2024.3(137).489-497
Views:
15
Email this article 