# American Institute of Mathematical Sciences

doi: 10.3934/amc.2022048
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## Estimate of 4-adic complexity of unified quaternary sequences of length $2p$

 Department of Applied Mathematics and Informatics, Yaroslav-the-Wise Novgorod State University, Veliky Novgorod 173003, Russia

Received  February 2022 Revised  May 2022 Early access July 2022

Fund Project: V. Edemskiy and S. Koltsova were supported by Russian Science Foundation according to the research project No. 22-21-00516

We derive the 4-adic complexity of unified quaternary sequences with period $2p$. These sequences with good autocorrelation properties are proposed by Ke et al. in 2020. We estimate the 4-adic complexity of aforementioned sequences and show that any of them has high 4-adic complexity, which is good enough to resist the attack of the rational approximation algorithm.

Citation: Vladimir Edemskiy, Sofia Koltsova. Estimate of 4-adic complexity of unified quaternary sequences of length $2p$. Advances in Mathematics of Communications, doi: 10.3934/amc.2022048
##### References:
 [1] T. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, North-Holland mathematical library, Elsevier, 2004. [2] C. Ding, T. Helleseth and H. M. Martinsen, New families of binary sequences with optimal three-level autocorrelation, IEEE Trans. Inf. Theory, 47 (2001), 428-433.  doi: 10.1109/18.904555. [3] V. Edemskiy and A. Ivanov, Autocorrelation and linear complexity of quaternary sequences of period $2p$ based on cyclotomic classes of order four, IEEE International Symposium on Information Theory, (2013), 3120–3124. [4] V. Edemskiy and Y. Sun, The symmetric 2-adic complexity of sequences with optimal autocorrelation magnitude and length $8q$, Cryptogr. Commun., 14 (2022), 183-199.  doi: 10.1007/s12095-021-00503-0. [5] M. Goresky and A. Klapper, Algebraic Shift Register Sequences, Cambridge University Press, 2012. [6] H. Hu and D. Feng, On the 2-adic complexity and the k-error 2-adic complexity of periodic binary sequences, IEEE Trans. Inf. Theory, 54 (2008), 874-883.  doi: 10.1109/TIT.2007.913238. [7] X. Jing, M. Yang and K. Feng, 4-adic complexity of interleaved quaternary sequences, preprint, arXiv: 2105.13826v1, [cs.IT] 28 May 2021. [8] P. Ke, P. Qiao and Y. Yang, On the equivalence of several classes of quaternary sequences with optimal autocorrelation and length $2p$, Adv. Math. Commun., 16 (2022), 285-302.  doi: 10.3934/amc.2020112. [9] Y. S. Kim, J. W. Jang, S. H. Kim and J. S. No, New construction of quaternary sequences with ideal autocorrelation from Legendre sequences, Proc. ISIT, Seoul, Korea, (2009), 282–285. [10] Y. S. Kim, J. W. Jang, S. H. Kim and J. S. No, New quaternary sequences with optimal autocorrelation, Proc. ISIT, Seoul, Korea, (2009), 286–289. [11] A. Klapper, A survey of feedback with carry shift registers, Sequences and Their Applications-SETA 2004, Springer Berlin Heidelberg, (2005), 56–71. [12] A. Klapper and J. Xu, Register synthesis for algebraic feedback shift registers based on non-primes, Des. Codes Cryptogr., 31 (2004), 227-250.  doi: 10.1023/B:DESI.0000015886.71135.e1. [13] L. F. Luo and W. P. Ma, Balanced quaternary sequences of even period with optimal autocorrelation, IET Commun., 13 (2019), 1808-1812. [14] S. Qiang, Y. Li, M. Yang and K. Feng, The 4-adic complexity of a class of quaternary cyclotomic sequences with period $2p$, preprint, CoRR abs/2011.11875, (2020). [15] X. Shen, Y. Jia, J. Wang and L. Zhang, New families of balanced quaternary sequences of even period with three-level optimal autocorrelation, IEEE Commun. Lett., 21 (2017), 2146-2149. [16] W. Su, et al., New quaternary sequences of even length with optimal autocorrelation, Sci. China (Inf. Sci.), 61 (2018), 022308, 13 pp. doi: 10.1007/s11432-016-9087-2. [17] J. Xu and A. Klapper, Feedback with carry shift registers over $\mathbb{Z}/(N)$, Sequences and Their Applications. Discrete Mathematics and Theoretical Computer Science, (1998), 379–392. [18] M. Yang, S. Qiang, X. Jing, K. Feng and D. Lin, On the 4-adic complexity of quaternary sequences with ideal autocorrelation, preprint, arXiv: 2107.03574v2, [cs.IT], 13 Jul 2021. [19] L. Zhang, J. Zhang, M. Yang and K. Feng, On the 2-adic complexity of the Ding-Helleseth-Martinsen binary sequences, IEEE Trans. Inform. Theory, 66 (2020), 4613-4620.  doi: 10.1109/TIT.2020.2964171.

show all references

##### References:
 [1] T. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, North-Holland mathematical library, Elsevier, 2004. [2] C. Ding, T. Helleseth and H. M. Martinsen, New families of binary sequences with optimal three-level autocorrelation, IEEE Trans. Inf. Theory, 47 (2001), 428-433.  doi: 10.1109/18.904555. [3] V. Edemskiy and A. Ivanov, Autocorrelation and linear complexity of quaternary sequences of period $2p$ based on cyclotomic classes of order four, IEEE International Symposium on Information Theory, (2013), 3120–3124. [4] V. Edemskiy and Y. Sun, The symmetric 2-adic complexity of sequences with optimal autocorrelation magnitude and length $8q$, Cryptogr. Commun., 14 (2022), 183-199.  doi: 10.1007/s12095-021-00503-0. [5] M. Goresky and A. Klapper, Algebraic Shift Register Sequences, Cambridge University Press, 2012. [6] H. Hu and D. Feng, On the 2-adic complexity and the k-error 2-adic complexity of periodic binary sequences, IEEE Trans. Inf. Theory, 54 (2008), 874-883.  doi: 10.1109/TIT.2007.913238. [7] X. Jing, M. Yang and K. Feng, 4-adic complexity of interleaved quaternary sequences, preprint, arXiv: 2105.13826v1, [cs.IT] 28 May 2021. [8] P. Ke, P. Qiao and Y. Yang, On the equivalence of several classes of quaternary sequences with optimal autocorrelation and length $2p$, Adv. Math. Commun., 16 (2022), 285-302.  doi: 10.3934/amc.2020112. [9] Y. S. Kim, J. W. Jang, S. H. Kim and J. S. No, New construction of quaternary sequences with ideal autocorrelation from Legendre sequences, Proc. ISIT, Seoul, Korea, (2009), 282–285. [10] Y. S. Kim, J. W. Jang, S. H. Kim and J. S. No, New quaternary sequences with optimal autocorrelation, Proc. ISIT, Seoul, Korea, (2009), 286–289. [11] A. Klapper, A survey of feedback with carry shift registers, Sequences and Their Applications-SETA 2004, Springer Berlin Heidelberg, (2005), 56–71. [12] A. Klapper and J. Xu, Register synthesis for algebraic feedback shift registers based on non-primes, Des. Codes Cryptogr., 31 (2004), 227-250.  doi: 10.1023/B:DESI.0000015886.71135.e1. [13] L. F. Luo and W. P. Ma, Balanced quaternary sequences of even period with optimal autocorrelation, IET Commun., 13 (2019), 1808-1812. [14] S. Qiang, Y. Li, M. Yang and K. Feng, The 4-adic complexity of a class of quaternary cyclotomic sequences with period $2p$, preprint, CoRR abs/2011.11875, (2020). [15] X. Shen, Y. Jia, J. Wang and L. Zhang, New families of balanced quaternary sequences of even period with three-level optimal autocorrelation, IEEE Commun. Lett., 21 (2017), 2146-2149. [16] W. Su, et al., New quaternary sequences of even length with optimal autocorrelation, Sci. China (Inf. Sci.), 61 (2018), 022308, 13 pp. doi: 10.1007/s11432-016-9087-2. [17] J. Xu and A. Klapper, Feedback with carry shift registers over $\mathbb{Z}/(N)$, Sequences and Their Applications. Discrete Mathematics and Theoretical Computer Science, (1998), 379–392. [18] M. Yang, S. Qiang, X. Jing, K. Feng and D. Lin, On the 4-adic complexity of quaternary sequences with ideal autocorrelation, preprint, arXiv: 2107.03574v2, [cs.IT], 13 Jul 2021. [19] L. Zhang, J. Zhang, M. Yang and K. Feng, On the 2-adic complexity of the Ding-Helleseth-Martinsen binary sequences, IEEE Trans. Inform. Theory, 66 (2020), 4613-4620.  doi: 10.1109/TIT.2020.2964171.
$(p-1)/4$ is odd
 $(i,j)_4$ 0 1 2 3 0 $A$ $B$ $C$ $D$ 1 $E$ $E$ $D$ $B$ 2 $A$ $E$ $A$ $E$ 3 $E$ $D$ $B$ $E$
 $(i,j)_4$ 0 1 2 3 0 $A$ $B$ $C$ $D$ 1 $E$ $E$ $D$ $B$ 2 $A$ $E$ $A$ $E$ 3 $E$ $D$ $B$ $E$
$(p-1)/4$ is even
 $(i,j)_4$ 0 1 2 3 0 $F$ $G$ $K$ $I$ 1 $G$ $I$ $J$ $J$ 2 $K$ $J$ $K$ $J$ 3 $I$ $J$ $J$ $G$
 $(i,j)_4$ 0 1 2 3 0 $F$ $G$ $K$ $I$ 1 $G$ $I$ $J$ $J$ 2 $K$ $J$ $K$ $J$ 3 $I$ $J$ $J$ $G$
 [1] Fuqing Sun, Qin Yue, Xia Li. on the 2-adic complexity of cyclotomic binary sequences of order three. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022049 [2] Lin Yi, Xiangyong Zeng, Zhimin Sun, Shasha Zhang. On the linear complexity and autocorrelation of generalized cyclotomic binary sequences with period $4p^n$. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021019 [3] Nian Li, Xiaohu Tang, Tor Helleseth. A class of quaternary sequences with low correlation. Advances in Mathematics of Communications, 2015, 9 (2) : 199-210. doi: 10.3934/amc.2015.9.199 [4] Andrew Klapper. The asymptotic behavior of N-adic complexity. Advances in Mathematics of Communications, 2007, 1 (3) : 307-319. doi: 10.3934/amc.2007.1.307 [5] Zhifan Ye, Zhengchun Zhou, Yang Yang, Tor Helleseth. New Classes of Asymptotically Optimal Spectrally-Constrained Sequences Derived from Cyclotomy. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022054 [6] Pinhui Ke, Yueqin Jiang, Zhixiong Chen. On the linear complexities of two classes of quaternary sequences of even length with optimal autocorrelation. Advances in Mathematics of Communications, 2018, 12 (3) : 525-539. doi: 10.3934/amc.2018031 [7] Yang Yang, Guang Gong, Xiaohu Tang. On $\omega$-cyclic-conjugated-perfect quaternary GDJ sequences. Advances in Mathematics of Communications, 2016, 10 (2) : 321-331. doi: 10.3934/amc.2016008 [8] Büşra Özden, Oǧuz Yayla. Partial direct product difference sets and almost quaternary sequences. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021010 [9] Jiarong Peng, Xiangyong Zeng, Zhimin Sun. Finite length sequences with large nonlinear complexity. Advances in Mathematics of Communications, 2018, 12 (1) : 215-230. doi: 10.3934/amc.2018015 [10] Pinhui Ke, Panpan Qiao, Yang Yang. On the equivalence of several classes of quaternary sequences with optimal autocorrelation and length $2p$. Advances in Mathematics of Communications, 2022, 16 (2) : 285-302. doi: 10.3934/amc.2020112 [11] Liqin Hu, Qin Yue, Fengmei Liu. Linear complexity of cyclotomic sequences of order six and BCH codes over GF(3). Advances in Mathematics of Communications, 2014, 8 (3) : 297-312. doi: 10.3934/amc.2014.8.297 [12] Zhixiong Chen, Vladimir Edemskiy, Pinhui Ke, Chenhuang Wu. On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, 12 (4) : 805-816. doi: 10.3934/amc.2018047 [13] Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016 [14] Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036 [15] Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $k$-error linear complexity for $p^n$-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018 [16] Lin Yi, Xiangyong Zeng, Zhimin Sun. On finite length nonbinary sequences with large nonlinear complexity over the residue ring $\mathbb{Z}_{m}$. Advances in Mathematics of Communications, 2021, 15 (4) : 701-720. doi: 10.3934/amc.2020091 [17] Sarah Bailey Frick. Limited scope adic transformations. Discrete and Continuous Dynamical Systems - S, 2009, 2 (2) : 269-285. doi: 10.3934/dcdss.2009.2.269 [18] James Kingsbery, Alex Levin, Anatoly Preygel, Cesar E. Silva. Dynamics of the $p$-adic shift and applications. Discrete and Continuous Dynamical Systems, 2011, 30 (1) : 209-218. doi: 10.3934/dcds.2011.30.209 [19] Ronnie Pavlov, Pascal Vanier. The relationship between word complexity and computational complexity in subshifts. Discrete and Continuous Dynamical Systems, 2021, 41 (4) : 1627-1648. doi: 10.3934/dcds.2020334 [20] Ferenc Szöllősi. On quaternary complex Hadamard matrices of small orders. Advances in Mathematics of Communications, 2011, 5 (2) : 309-315. doi: 10.3934/amc.2011.5.309

2021 Impact Factor: 1.015