О симметричной 2-адической сложности чередующихся последовательностей на основе последовательностей Лежандра
https://doi.org/10.34680/2076-8052.2024.3(137).489-497
Аннотация
2-адическая сложность, наряду с линейной сложностью, являются важными характеристиками псевдослучайных последовательностей, значимыми для их практических приложений. Для оценки непредсказуемости бинарных последовательностей предпочтительнее симметричная 2-адическая сложность, которая определяется как наименьшая из 2-адической сложности последовательности и 2-адической сложности последовательности, записанной в обратном порядке. В статье исследуется симметричная 2-адическая сложность чередующихся бинарных последовательностей, обладающих высокой линейной сложностью и хорошими автокорреляционными свойствами. Для определения рассматриваемых последовательностей используются циклические сдвиги последовательностей Лежандра и их дополнения. Показано, что для этих последовательностей симметричная 2-адическая сложность близка к максимально возможной и достаточна для отражения атак посредством алгоритма рациональной апроксимации. Метод исследования основан на анализе соотношения между периодической автокорреляционной функции последовательности, значения которой известны, и порождающего многочлена последовательности, инверсной к искомой.
Ключевые слова
бинарные последовательности,
симметричная 2-адическая сложность,
чередование последовательностей Лежандра
При поддержке: Работа выполнена при поддержке Российского научного фонда, проект № 24–21–00442
Об авторах
В. А. Едемский
Новгородский государственный университет имени Ярослава Мудрого
Россия
Россия
Едемский Владимир Анатольевич – доктор физико-математических наук, доцент, заведующий кафедрой.
Великий Новгород
Д. С. Дроганова
Новгородский государственный университет имени Ярослава Мудрого
Россия
Россия
Дроганова Дарья Сергеевна – студент.
Великий Новгород
Список литературы
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
Рецензия
Для цитирования:
Едемский В.А., Дроганова Д.С. О симметричной 2-адической сложности чередующихся последовательностей на основе последовательностей Лежандра. Вестник Новгородского государственного университета. 2024;(3(137)):489-497. https://doi.org/10.34680/2076-8052.2024.3(137).489-497
For citation:
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
Просмотров:
14
Послать статью по эл. почте 