Symmetric 2-adic complexity of binary sequences with period 4q and optimal autocorrelation magnitude
https://doi.org/10.34680/2076-8052.2021.2(123).47-51
Abstract
Binary sequences with a period of 4q (where q is an odd prime) and an optimal autocorrelation magnitude are considered. Sequences are defined using prime modulus biquadratic residue classes and direct product of residue class rings. It is shown that they have a high symmetric 2-adic complexity. The 2-adic complexity of a sequence is defined as the smallest number of carry-feedback shift register cells that is capable to generate a sequence. Symmetric 2-adic complexity is preferred over 2-adic complexity when evaluating the unpredictability of binary sequences. The research method is based on the application of generalized Gaussian sums over rings of residue classes. Binary sequences with high linear and 2-adic complexity and good autocorrelation properties are of interest for cryptographic applications, in particular, for stream encryption.
About the Authors
V. A. Edemskiy
Новгородский государственный университет имени Ярослава Мудрого
Russian Federation
Russian Federation
A. V. Ivanov
Новгородский государственный университет имени Ярослава Мудрого
Russian Federation
Russian Federation
References
1. Sun Y., Shen H. New Binary Sequences of Length 4р with Optimal Autocorrelation Magnitude // Ars Combinatoria (A Canadian Journal of Combinatorics). 2008. V. LXXXIX (89). P.255-262.
2. Lidl R., Niederreiter Н. Finite Fields. Addison-Wesley, 1983, 812 p. (Rus. ed.: Konechnye polya. Moscow, Mir Publ., 1988. 820 p).
3. Klapper A., Goresky M. Feedback shift registers, 2-adic span, and combiners with memory. Journal of Cryptology, 1997, vol.10, pp.111-147.
4. Klapper A., Goresky M. Cryptanalysis based on 2-adic rational approximation. LNCS, 1995, vol.963, pp.262-273.
5. Sun Y, Wang Q., Yan T. The exact autocorrelation distribution and 2-adic complexity of a class of binary sequences with almost optimal autocorrelation. Cryptography and Communications, 2018, vol.10 (3), pp.467-477.
6. Sun Y., Yan T., Chen Z. The 2-adic complexity of a class of binary sequences with optimal autocorrelation magnitude. Cryptography and Communications, 2020, vol.12, pp.675-683.
7. Xiao Z., Zeng X., Sun Z. 2-Adic complexity of two classes of generalized cyclotomic binary sequences. Internationl Journal of Foundations of Comput. Sci., 2016, vol.27 (7), pp.879-893.
8. Xiong H., Qu L., Li C. A new method to compute the 2-adic complexity of binary sequences. IEEE Trans. Inform. Theory, 2014, vol.60, pp.2399-2406.
9. Xiong H., Qu L., Li C. 2-Adic complexity of binary sequences with interleaved structure. Finite Fields and Their Applications, 2015, vol.33, pp.14-28.
10. Hu H., Feng D. On the 2-adic complexity and the k-error 2-adic complexity of periodic binary sequences. IEEE Trans. Inf. Theory, 2008, vol.54(2), pp.874-883.
11. Edemskiy V.A., Antonova O.V. On symmetric 2-adic complexity of binary sequences based on biquadratic residues. Mathematical methods in engineering and technology: Proc. of int. conf. Saint Petersburg, Publishing house of Polytechnic university, 2020, vol.12 (2), pp.79-81.
12. Lineynaya slozhnost' obobshchennykh tsiklotomicheskikh posledovatel'nostey s periodom 2mpn [Linear complexity of generalized cyclotomic sequences with period 2mpn]. Prikladnaya diskretnaya matematika, 2012, no.3(17), pp.5-12.
13. Cusick T., Ding C., Renvall A. Stream Ciphers and Number Theory. Elsevier Science, 2004. 492 p.
14. Zhang L., Zhang J., Yang M., Feng K. On the 2-Adic Complexity of the Ding-Helleseth-Martinsen Binary Sequences // IEEE Trans. Inform. Theory. 2020. DOI:10.1109/TIT.2020.2964171
15. Ding C., Helleseth T., Martinsen H. New families of binary sequences with optimal three-valued autocorrelation. IEEE Trans. Inf. Theory, 2001, vol.47(1), pp.428-433.
Review
For citations:
Edemskiy V.A., Ivanov A.V. Symmetric 2-adic complexity of binary sequences with period 4q and optimal autocorrelation magnitude. Title in english. 2021;(2(123)):47-51. (In Russ.) https://doi.org/10.34680/2076-8052.2021.2(123).47-51
Views:
43
Email this article 