vestnovsuВестник Новгородского государственного университетаVestnik of Novgorod State University2076-8052Новгородский государственный университет имени Ярослава Мудрого10.34680/2076-8052.2024.3(137).489-497vestnovsu-351Research ArticleРАДИОТЕХНИКА И СВЯЗЬRADIOTECHNICS AND TELECOMMUNICATIONSО симметричной 2-адической сложности чередующихся последовательностей на основе последовательностей ЛежандраAbout symmetric 2-adic complexity of interleaving sequences based on Legendre sequenceshttps://orcid.org/0000-0003-1368-3827ЕдемскийВ. А.EdemskiyV. A.

Едемский Владимир Анатольевич – доктор физико-математических наук, доцент, заведующий кафедрой.

Великий Новгород

Veliky Novgorod

Vladimir.Edemsky@novsu.ruhttps://orcid.org/0009-0000-5010-026XДрогановаД. С.DroganovaD. S.

Дроганова Дарья Сергеевна – студент.

Великий Новгород

Veliky Novgorod

darya.droganova@gmail.comНовгородский государственный университет имени Ярослава МудрогоРоссияYaroslav-the-Wise Novgorod State UniversityRussian Federation20241303202503(137)489497Copyright © Едемский В.А., Дроганова Д.С., 20252025Едемский В.А., Дроганова Д.С.Edemskiy V.A., Droganova D.S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnovsu.elpub.ru/jour/article/view/351

2-адическая сложность, наряду с линейной сложностью, являются важными характеристиками псевдослучайных последовательностей, значимыми для их практических приложений. Для оценки непредсказуемости бинарных последовательностей предпочтительнее симметричная 2-адическая сложность, которая определяется как наименьшая из 2-адической сложности последовательности и 2-адической сложности последовательности, записанной в обратном порядке. В статье исследуется симметричная 2-адическая сложность чередующихся бинарных последовательностей, обладающих высокой линейной сложностью и хорошими автокорреляционными свойствами. Для определения рассматриваемых последовательностей используются циклические сдвиги последовательностей Лежандра и их дополнения. Показано, что для этих последовательностей симметричная 2-адическая сложность близка к максимально возможной и достаточна для отражения атак посредством алгоритма рациональной апроксимации. Метод исследования основан на анализе соотношения между периодической автокорреляционной функции последовательности, значения которой известны, и порождающего многочлена последовательности, инверсной к искомой.

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.

бинарные последовательностисимметричная 2-адическая сложностьчередование последовательностей Лежандраbinary sequencessymmetric 2-adic complexityinterleaving Legendre sequencesРабота выполнена при поддержке Российского научного фонда, проект № 24–21–00442ReferencesKlapper A., Goresky M. Feedback shift registers, 2-adic span, and combiners with memory // Journal of Cryptology. 1997. 10 (2). 111-147. DOI: 10.1007/s001459900024Klapper A., Goresky M. Feedback shift registers, 2-adic span, and combiners with memory // Journal of Cryptology. 1997. 10 (2). 111-147. DOI: 10.1007/s001459900024Goresky M., Klapper A. Algebraic Shift Register Sequences. Cambridge: Cambridge University Press, 2012.Goresky M., Klapper A. Algebraic Shift Register Sequences. Cambridge: Cambridge University Press, 2012.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.2964171Zhang 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.2964171Sun 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-3Sun 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-3Sun 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.2022049Sun 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.2022049Xiao 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/S0129054116500350Xiao 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/S0129054116500350Hu 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.913238Hu 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.913238Xiao 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.2022088Xiao 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.2022088Edemskiy 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.2023017Edemskiy 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.2023017Tang 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.2039159Tang 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.2039159Li 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.2159575Li 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.2159575Xiong 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.009Xiong 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.009Xiao 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-8Xiao 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-8Wang 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.2079550Wang 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

The authors declare that there are no conflicts of interest present.