2-адическая сложность бинарных последовательностей Динга – Хеллесета с периодом pq
https://doi.org/10.26907/2541-7746.2025.2.213-226
Аннотация
Предложен метод анализа 2-адической сложности бинарных обобщенных циклотомических последовательностей с периодом pq. 2-адическая сложность, наряду с линейной сложностью, является важной характеристикой непредсказуемости последовательностей. Метод основан на использовании обобщенных гауссовых периодов различных порядков по простым модулям p и q. Оценена 2-адическая сложность обобщенных циклотомических последовательностей Динга – Хеллесета второго, четвертого и шестого порядков с высокой линейной сложностью. Показано, что рассмотренные последовательности обладают большой 2-адической сложностью, достаточной для отражения атак посредством алгоритма рациональной аппроксимации. Обобщены предыдущие результаты, полученные для последовательностей второго порядка.
Рассмотренный метод может быть использован для последовательностей другого вида, которые определяются посредством использования обобщенных циклотомических классов разных порядков. Его также можно применять для анализа m-адической сложности как бинарных, так и небинарных последовательностей, например, четвертичных.
При поддержке: Исследование выполнено при финансовой поддержке Российского научного фонда, проект № 24-21-00442.
Об авторе
В. А. Едемский
Новгородский государственный университет им. Ярослава Мудрого
Россия
Россия
Владимир Анатольевич Едемский, доктор физико-математических наук, доцент, профессор кафедры «Прикладная математика и информатика»
г. Великий Новгород
Список литературы
1. Klapper A., Goresky M. Feedback shift registers, 2-adic span, and combiners with memory // J. Cryptol. 1997. V. 10, No 2. P. 111–147. https://doi.org/10.1007/s001459900024.
2. Goresky M., Klapper A. Algebraic Shift Register Sequences. Cambridge: Cambridge Univ. Press, 2012. xvi, 498 p. https://doi.org/10.1017/CBO9781139057448.
3. Hu H. Comments on “a new method to compute the 2-adic complexity of binary sequences” // IEEE Trans. Inf. Theory. 2014. V. 60, No 9. P. 5803–5804. https://doi.org/10.1109/TIT.2014.2336843.
4. Sun Y., Wang O., Yan T. The exact autocorrelation distribution and 2-adic complexity of a class of binary sequences with almost optimal autocorrelation // Cryptogr. Commun. 2018. V. 10, No 3. P. 467–477. https://doi.org/10.1007/s12095-017-0233-x.
5. Sun Y., Yan T., Chen Z. The 2-adic complexity of a class of binary sequences with optimal autocorrelation magnitude // Cryptogr. Commun. 2020. V. 12, No 4. P. 675–683. https://doi.org/10.1007/s12095-019-00411-4.
6. Xiao Z., Zeng X. 2-Adic complexity of two constructions of binary sequences with period 4N and optimal autocorrelation magnitude // Cryptogr. Commun. 2021. V. 13, No 5. P. 865—885. https://doi.org/10.1007/s12095-021-00498-8.
7. Yan F., Ke P., Chang Z. The symmetric 2-adic complexity of Tang–Gong interleaved sequences from Legendre sequence pair // Cryptogr. Commun. 2025. V. 17, No 1. P. 167—179. https://doi.org/10.1007/s12095-024-00751-w.
8. Xiao Z., Zeng X., Ke M. On the symmetric 2-adic complexity of periodic binary sequences // Adv. Math. Commun. 2024. V. 18, No 5. P. 1303–1314. https://doi.org/10.3934/amc.2022088.
9. Hofer R., Winterhof A. On the 2-adic complexity of the two-prime generator // IEEE Trans. Inf. Theory. 2018. V. 64, No 8. P. 5957–5960. https://doi.org/10.1109/TIT.2018.2811507.
10. Xiao Z., Zeng X., Sun Z. 2-Adic complexity of two classes of generalized cyclotomic binary sequences // Int. J. Found. Comput. Sci. 2016. V. 27, No 7. P. 879–893. https://doi.org/10.1142/S0129054116500350.
11. Sun Y., Wang Q., Yan T. A lower bound on the 2-adic comeplxity of the modified Jacobi sequences // Cryptogr. Commun. 2019. V. 11, No 2. P. 337–349. https://doi.org/10.1007/s12095-018-0300-y.
12. Zhang L., Zhang J., Yang M., Feng K. On the 2-adic complexity of the Ding–Helleseth–Martinsen binary sequences // IEEE Trans. Inf. Theory. 2020. V. 66, No 7. P. 4613–4620. https://doi.org/10.1109/TIT.2020.2964171.
13. Yan M., Yan T., Li Y. Computing the 2-adic complexity of two classes of Ding–Helleseth generalized cyclotomic sequences of periods of twin prime products // Cryptogr. Commun. 2021. V. 13, No 1. P. 15—26. https://doi.org/10.1007/s12095-020-00451-1.
14. Yan T., Yan M., Sun Y., Sun S. The 2-Adic Complexity of Ding–Helleseth Generalized Cyclotomic Sequences of Order 2 and Period pq // IEEE Access. 2020. V. 8. P. 140682–140687. https://doi.org/10.1109/ACCESS.2020.3012570.
15. Xiong H., Qu L., Li C. A new method to compute the 2-adic complexity of binary sequences // IEEE Trans. Inf. Theory. 2014. V. 60, No 4. P. 2399–2406. https://doi.org/10.1109/TIT.2014.2304451.
16. Ma J., Zhao W., Jia Y., Shen X., Jiang H. Linear complexity and trace representation of new Ding generalized cyclotomic sequences with period pq and order two // Mathematics. 2021. V. 9, No 18. Art. 2285. https://doi.org/10.3390/math9182285.
17. Ding C., Helleseth T. New generalized cyclotomy and its applications // Finite Fields. 1998. V. 4, No 2. P. 140–166. https://doi.org/10.1006/ffta.1998.0207.
18. Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. М.: Мир, 1987. 416 с.
19. Edemskiy V., Wu C. Symmetric 2-adic complexity of Ding-Helleseth generalized cyclotomic sequences of period pq // Wu Y., Yung M. (Eds.) Information Security and Cryptology: Inscrypt 2020. Ser.: Lecture Notes in Computer Science. V. 12612. Cham: Springer, 2021. P. 318–327. https://doi.org/10.1007/978-3-030-71852-7_21.
20. Edemskiy V.A., Koltsova S.A. Symmetric 2-adic complexity of generalized cyclotomic sequences of order six with period pq // J. Phys.: Conf. Ser. 2021. V. 2052. Art. 012009. https://doi.org/10.1088/1742-6596/2052/1/012009.
21. Ma J., Zhao W., Jia Y., Jiang H. New generalized cyclotomic quaternary sequences with large linear complexity and a product of two primes period // Information. 2021. V. 12, No 5. Art. 193. https://doi.org/10.3390/info12050193.
Рецензия
Для цитирования:
Едемский В.А. 2-адическая сложность бинарных последовательностей Динга – Хеллесета с периодом pq. Ученые записки Казанского университета. Серия Физико-математические науки. 2025;167(2):213-226. https://doi.org/10.26907/2541-7746.2025.2.213-226
For citation:
Edemskiy V.A. 2-Adic complexity of Ding–Helleseth binary sequences with period pq. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki. 2025;167(2):213-226. (In Russ.) https://doi.org/10.26907/2541-7746.2025.2.213-226
Просмотров:
27
Послать статью по эл. почте 