2-Adic complexity of Ding–Helleseth binary sequences with period pq
https://doi.org/10.26907/2541-7746.2025.2.213-226
Abstract
A method is proposed to analyze the 2-adic complexity of generalized cyclotomic binary sequences with period pq. Along with linear complexity, 2-adic complexity serves as an important measure of sequence unpredictability. The method is based on generalized Gaussian periods of various orders using the prime modules p and q. The 2-adic complexity of Ding–Helleseth generalized cyclotomic sequences of orders two, four, and six with high linear complexity is estimated. The analysis shows that these sequences have high 2-adic complexity, which is sufficient to resist attacks using the rational approximation algorithm. Previous results obtained for the sequences of order two are summarized. The proposed method can be applied to a different type of sequences defined using generalized cyclotomic classes of various orders, as well as to investigate the m-adic complexity of both binary and non-binary sequences, such as quaternary sequences.
Supporting agencies: This study was supported by the Russian Science Foundation (project no. 24-21-00442).
About the Author
V. A. Edemskiy
Yaroslav-the-Wise Novgorod State University
Russian Federation
Russian Federation
Vladimir A. Edemskiy, Doc. Sci. (Physics and Mathematics), Professor, Department of Applied Mathematics and Informatics
Veliky Novgorod
References
1. Klapper A., Goresky M. Feedback shift registers, 2-adic span, and combiners with memory. J. Cryptol., 1997, vol. 10, no. 2, pp. 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, vol. 60, no. 9, pp. 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, vol. 10, no. 3, pp. 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, vol. 12, no. 4, pp. 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, vol. 13, no. 5, pp. 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, vol. 17, no. 1, pp. 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, vol. 18, no. 5, pp. 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, vol. 64, no. 8, pp. 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, vol. 27, no. 7, pp. 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, vol. 11, no. 2, pp. 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, vol. 66, no. 7, pp. 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, vol. 13, no. 1, pp. 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, vol. 8, pp. 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, vol. 60, no. 4, pp. 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 and order two. Mathematics, 2021, vol. 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, vol. 4, no. 2, pp. 140–166. https://doi.org/10.1006/ffta.1998.0207.
18. Ireland K., Rosen M. Klassicheskoe vvedenie v sovremennuyu teoriyu chisel [A Classical Introduction to Modern Number Theory]. Moscow, Mir, 1987. 416 p. (In Russian)
19. Edemskiy V., Wu C. Symmetric 2-adic complexity of Ding-Helleseth generalized cyclotomic sequences of period pq. In: Wu Y., Yung M. (Eds.) Information Security and Cryptology: Inscrypt 2020. Ser.: Lecture Notes in Computer Science. Vol. 12612. Cham, Springer, 2021, pp. 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 pn . J. Phys.: Conf. Ser., 2021, vol. 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, vol. 12, no. 5, art. 193. https://doi.org/10.3390/info12050193.
Review
For citations:
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
Views:
26
Email this article 