doi: 10.3934/amc.2022049
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.

on the 2-adic complexity of cyclotomic binary sequences of order three

Department of Mathematics, Nanjing University of Aeronautics and Astronautics, Nanjing 211100, China

*Corresponding author: Qin Yue

Received  February 2022 Revised  May 2022 Early access July 2022

Fund Project: This work was supported in part by National Natural Science Foundation of China (No. 61772219, No. 12171420) and National Science Foundation of Shandong Province under Grant ZR2021MA046, and National Science Foundation of Jiangsu Province of China (No. BK20200268)

Let $ p\equiv 1\pmod 3 $ be a prime. In this paper, we determine the 2-adic complexity of all non-trivial balanced cyclotomic binary sequences of order three with period $ 2p $ and the 2-adic complexity of several non-balanced cyclotomic binary sequences of order three with period $ 2p $.

Citation: Fuqing Sun, Qin Yue, Xia Li. on the 2-adic complexity of cyclotomic binary sequences of order three. Advances in Mathematics of Communications, doi: 10.3934/amc.2022049
References:
[1]

H. CaiZ. ZhouY. Yang and X. Tang, A new construction of frequency-hopping sequences with optimal partial Hamming correlation, IEEE Trans. Inf. Theory, 60 (2014), 5782-5790.  doi: 10.1109/TIT.2014.2332996.

[2]

T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, North-Holland Mathematical Library, 55. North-Holland Publishing Co., Amsterdam, 1998.

[3]

L. E. Dickson, Cyclotomy, higher congruences, and waring's problem, Amer. J. Math., 57 (1935), 391-424.  doi: 10.2307/2371217.

[4]

C. DingT. Helleseth and K. Y. Lam, Several classes of binary sequences with three-level autocorrelation, IEEE Trans. Inf. Theory, 45 (1999), 2606-2612.  doi: 10.1109/18.796414.

[5]

C. DingT. Helleseth and H. Martinsen, New families of binary sequences with optimal three-level autocorrelation, IEEE Trans. Inf. Theory, 47 (2001), 428-433.  doi: 10.1109/18.904555.

[6]

C. DingY. Yang and X. Tang, Optimal sets of frequency hopping sequences from linear cyclic codes, IEEE Trans. Inf. Theory, 56 (2010), 3605-3612.  doi: 10.1109/TIT.2010.2048504.

[7]

S. W. Golomb, Shift Register Sequences, Holden-Day, San Francisco 1967.

[8]

T. Helleseth and P. V. Kumar, Sequences with low correlation, Handbook of Coding Theory, 1/2 (1998), 1765-1854. 

[9]

R. Hofer and A. Winterhof, On the 2-adic complexity of the two-prime generator, IEEE Trans. Inf. Theory, 64 (2018), 5957-5960.  doi: 10.1109/TIT.2018.2811507.

[10]

H. Hu, Comments on a new method to compute the 2-adic complexity of binary sequences, IEEE Trans. Inf. Theory, 60 (2014), 5803-5804.  doi: 10.1109/TIT.2014.2336843.

[11]

L. Hu and Q. Yue, Gauss periods and codebooks from generalized cyclotomic sets of order four, Des. Codes Cryptogr, 69 (2013), 233-246.  doi: 10.1007/s10623-012-9648-8.

[12]

A. Klapper and M. Goresky, Feedback shift registers, 2-adic span, and combiners with memory, J. Cryptol., 10 (1997), 111-147.  doi: 10.1007/s001459900024.

[13]

A. LempelM. Cohn and W. L. Eastman, A class of binary sequences with optimal autocorrelation properties, IEEE Trans. Inf. Theory, 23 (1977), 38-42.  doi: 10.1109/tit.1977.1055672.

[14]

X. ShiT. YanX. Huang and Q. Yue, An extension method to construct M-ary sequences of period $4$N with low autocorrelation, IEICE Trans. Fundam. Electron. Commun. Comput. Sci, 104 (2021), 332-335. 

[15]

M. K. Simon, J. K. Omura, R. A. Scholtz and B. K. Levitt, Spread spectrum communications. rockville, MD: Computer Sci, 1 (1985).

[16]

T. Storer, Cyclotomy and Difference Sets, Markham Pub. Co., 1967.

[17]

Y. SunQ. Wang and T. Yan, The exact autocorrelation distribution and 2-adic complexity of a class of binary sequences with almost optimal autocorrelation, Cryptogr. Commun, 10 (2018), 467-477.  doi: 10.1007/s12095-017-0233-x.

[18]

Y. SunQ. Wang and T. Yan, A lower bound on the 2-adic complexity of the modified Jacobi sequence, Cryptogr. Commun, 11 (2019), 337-349.  doi: 10.1007/s12095-018-0300-y.

[19]

Y. SunT. Yan and Z. Chen, The 2-adic complexity of a class of binary sequences with optimal autocorrelation magnitude, Cryptogr. Commun, 12 (2020), 675-683.  doi: 10.1007/s12095-019-00411-4.

[20]

X. Tang and C. Ding, New classes of balanced quaternary and almost balanced binary sequences with optimal autocorrelation value, IEEE Trans. Inf. Theory, 56 (2010), 6398-6405.  doi: 10.1109/TIT.2010.2081170.

[21]

X. Tang and G. Gong, New constructions of binary sequences with optimal autocorrelation value/magnitude, IEEE Trans. Inf. Theory, 56 (2010), 1278-1286.  doi: 10.1109/TIT.2009.2039159.

[22]

T. Tian and W. F. Qi, 2-adic complexity of binary m-sequences, IEEE Trans. Inf. Theory, 56 (2010), 450-454.  doi: 10.1109/TIT.2009.2034904.

[23]

A. L. Whiteman, The cyclotomic numbers of order twelve, Acta Arith, 6 (1960), 53-76.  doi: 10.4064/aa-6-1-53-76.

[24]

Z. XiaoX. Zeng and Z. Sun, 2-adic complexity of two classes of generalized cyclotomic binary sequences, Int. J. Found. Comput. Sci, 27 (2016), 879-893.  doi: 10.1142/S0129054116500350.

[25]

H. XiongL. Qu and C. Li, A new method to compute the 2-adic complexity of binary sequences, IEEE Trans. Inf. Theory, 60 (2014), 2399-2406.  doi: 10.1109/TIT.2014.2304451.

[26]

Y. Yang, F. Huo and G. Gong, Large zero odd periodic autocorrelation zone of Golay sequences and QAM Golay sequences, Proceedings of the 2012 International Symposium on Information Theory, Cambridge, MA, USA, (2012), 1024–1028.

[27]

Y. YangX. TangD. Peng and U. Parampalli, New bound on frequency hopping sequence sets and its optimal constructions, IEEE Trans. Inf. Theory, 57 (2011), 7605-7613.  doi: 10.1109/TIT.2011.2162571.

[28]

L. ZhangJ. ZhangM. Yang and K. Feng, On the 2-adic complexity of the Ding-Helleseth-Martinsen binary sequences, IEEE Trans. Inf. Theory, 66 (2010), 4613-4620.  doi: 10.1109/TIT.2020.2964171.

[29]

Z. ZhouT. Helleseth and U. Parampalli, A family of polyphase sequences with asymptotically optimal correlation, IEEE Trans. Inf. Theory, 64 (2010), 2896-2900.  doi: 10.1109/TIT.2018.2796597.

[30]

Z. ZhouX. Tang and G. Gong, A new class of sequences with zero or low correlation zone based on interleaving technique, IEEE Trans. Inf. Theory, 54 (2008), 4267-4273.  doi: 10.1109/TIT.2008.928256.

[31]

Z. ZhouX. TangX. Niu and U. Parampalli, New classes of frequency-hopping sequences with optimal partial correlation, IEEE Trans. Inf. Theory, 58 (2012), 453-458.  doi: 10.1109/TIT.2011.2167126.

[32]

Z. ZhouX. TangD. Peng and U. Parampalli, New constructions for optimal sets of frequency-hopping sequences, IEEE Trans. Inf. Theory, 57 (2011), 3831-3840.  doi: 10.1109/TIT.2011.2137290.

[33]

Z. ZhouD. ZhangT. Helleseth and J. Wen, A construction of multiple optimal ZCZ sequence sets with good cross correlation, IEEE Trans. Inf. Theory, 64 (2018), 1340-1346.  doi: 10.1109/TIT.2017.2756845.

show all references

References:
[1]

H. CaiZ. ZhouY. Yang and X. Tang, A new construction of frequency-hopping sequences with optimal partial Hamming correlation, IEEE Trans. Inf. Theory, 60 (2014), 5782-5790.  doi: 10.1109/TIT.2014.2332996.

[2]

T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, North-Holland Mathematical Library, 55. North-Holland Publishing Co., Amsterdam, 1998.

[3]

L. E. Dickson, Cyclotomy, higher congruences, and waring's problem, Amer. J. Math., 57 (1935), 391-424.  doi: 10.2307/2371217.

[4]

C. DingT. Helleseth and K. Y. Lam, Several classes of binary sequences with three-level autocorrelation, IEEE Trans. Inf. Theory, 45 (1999), 2606-2612.  doi: 10.1109/18.796414.

[5]

C. DingT. Helleseth and H. Martinsen, New families of binary sequences with optimal three-level autocorrelation, IEEE Trans. Inf. Theory, 47 (2001), 428-433.  doi: 10.1109/18.904555.

[6]

C. DingY. Yang and X. Tang, Optimal sets of frequency hopping sequences from linear cyclic codes, IEEE Trans. Inf. Theory, 56 (2010), 3605-3612.  doi: 10.1109/TIT.2010.2048504.

[7]

S. W. Golomb, Shift Register Sequences, Holden-Day, San Francisco 1967.

[8]

T. Helleseth and P. V. Kumar, Sequences with low correlation, Handbook of Coding Theory, 1/2 (1998), 1765-1854. 

[9]

R. Hofer and A. Winterhof, On the 2-adic complexity of the two-prime generator, IEEE Trans. Inf. Theory, 64 (2018), 5957-5960.  doi: 10.1109/TIT.2018.2811507.

[10]

H. Hu, Comments on a new method to compute the 2-adic complexity of binary sequences, IEEE Trans. Inf. Theory, 60 (2014), 5803-5804.  doi: 10.1109/TIT.2014.2336843.

[11]

L. Hu and Q. Yue, Gauss periods and codebooks from generalized cyclotomic sets of order four, Des. Codes Cryptogr, 69 (2013), 233-246.  doi: 10.1007/s10623-012-9648-8.

[12]

A. Klapper and M. Goresky, Feedback shift registers, 2-adic span, and combiners with memory, J. Cryptol., 10 (1997), 111-147.  doi: 10.1007/s001459900024.

[13]

A. LempelM. Cohn and W. L. Eastman, A class of binary sequences with optimal autocorrelation properties, IEEE Trans. Inf. Theory, 23 (1977), 38-42.  doi: 10.1109/tit.1977.1055672.

[14]

X. ShiT. YanX. Huang and Q. Yue, An extension method to construct M-ary sequences of period $4$N with low autocorrelation, IEICE Trans. Fundam. Electron. Commun. Comput. Sci, 104 (2021), 332-335. 

[15]

M. K. Simon, J. K. Omura, R. A. Scholtz and B. K. Levitt, Spread spectrum communications. rockville, MD: Computer Sci, 1 (1985).

[16]

T. Storer, Cyclotomy and Difference Sets, Markham Pub. Co., 1967.

[17]

Y. SunQ. Wang and T. Yan, The exact autocorrelation distribution and 2-adic complexity of a class of binary sequences with almost optimal autocorrelation, Cryptogr. Commun, 10 (2018), 467-477.  doi: 10.1007/s12095-017-0233-x.

[18]

Y. SunQ. Wang and T. Yan, A lower bound on the 2-adic complexity of the modified Jacobi sequence, Cryptogr. Commun, 11 (2019), 337-349.  doi: 10.1007/s12095-018-0300-y.

[19]

Y. SunT. Yan and Z. Chen, The 2-adic complexity of a class of binary sequences with optimal autocorrelation magnitude, Cryptogr. Commun, 12 (2020), 675-683.  doi: 10.1007/s12095-019-00411-4.

[20]

X. Tang and C. Ding, New classes of balanced quaternary and almost balanced binary sequences with optimal autocorrelation value, IEEE Trans. Inf. Theory, 56 (2010), 6398-6405.  doi: 10.1109/TIT.2010.2081170.

[21]

X. Tang and G. Gong, New constructions of binary sequences with optimal autocorrelation value/magnitude, IEEE Trans. Inf. Theory, 56 (2010), 1278-1286.  doi: 10.1109/TIT.2009.2039159.

[22]

T. Tian and W. F. Qi, 2-adic complexity of binary m-sequences, IEEE Trans. Inf. Theory, 56 (2010), 450-454.  doi: 10.1109/TIT.2009.2034904.

[23]

A. L. Whiteman, The cyclotomic numbers of order twelve, Acta Arith, 6 (1960), 53-76.  doi: 10.4064/aa-6-1-53-76.

[24]

Z. XiaoX. Zeng and Z. Sun, 2-adic complexity of two classes of generalized cyclotomic binary sequences, Int. J. Found. Comput. Sci, 27 (2016), 879-893.  doi: 10.1142/S0129054116500350.

[25]

H. XiongL. Qu and C. Li, A new method to compute the 2-adic complexity of binary sequences, IEEE Trans. Inf. Theory, 60 (2014), 2399-2406.  doi: 10.1109/TIT.2014.2304451.

[26]

Y. Yang, F. Huo and G. Gong, Large zero odd periodic autocorrelation zone of Golay sequences and QAM Golay sequences, Proceedings of the 2012 International Symposium on Information Theory, Cambridge, MA, USA, (2012), 1024–1028.

[27]

Y. YangX. TangD. Peng and U. Parampalli, New bound on frequency hopping sequence sets and its optimal constructions, IEEE Trans. Inf. Theory, 57 (2011), 7605-7613.  doi: 10.1109/TIT.2011.2162571.

[28]

L. ZhangJ. ZhangM. Yang and K. Feng, On the 2-adic complexity of the Ding-Helleseth-Martinsen binary sequences, IEEE Trans. Inf. Theory, 66 (2010), 4613-4620.  doi: 10.1109/TIT.2020.2964171.

[29]

Z. ZhouT. Helleseth and U. Parampalli, A family of polyphase sequences with asymptotically optimal correlation, IEEE Trans. Inf. Theory, 64 (2010), 2896-2900.  doi: 10.1109/TIT.2018.2796597.

[30]

Z. ZhouX. Tang and G. Gong, A new class of sequences with zero or low correlation zone based on interleaving technique, IEEE Trans. Inf. Theory, 54 (2008), 4267-4273.  doi: 10.1109/TIT.2008.928256.

[31]

Z. ZhouX. TangX. Niu and U. Parampalli, New classes of frequency-hopping sequences with optimal partial correlation, IEEE Trans. Inf. Theory, 58 (2012), 453-458.  doi: 10.1109/TIT.2011.2167126.

[32]

Z. ZhouX. TangD. Peng and U. Parampalli, New constructions for optimal sets of frequency-hopping sequences, IEEE Trans. Inf. Theory, 57 (2011), 3831-3840.  doi: 10.1109/TIT.2011.2137290.

[33]

Z. ZhouD. ZhangT. Helleseth and J. Wen, A construction of multiple optimal ZCZ sequence sets with good cross correlation, IEEE Trans. Inf. Theory, 64 (2018), 1340-1346.  doi: 10.1109/TIT.2017.2756845.

Table 1.  THE RELATIONS OF THE CYCLOTOMIC NUMBERS OF ORDER 3, $ p\equiv 1 \pmod 3 $
(i, j) 0 1 2
0 (0, 0) (0, 1) (0, 2)
1 (0, 1) (0, 2) (1, 2)
2 (0, 2) (1, 2) (0, 1)
(i, j) 0 1 2
0 (0, 0) (0, 1) (0, 2)
1 (0, 1) (0, 2) (1, 2)
2 (0, 2) (1, 2) (0, 1)
[1]

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

[2]

Frédéric Bernicot, Bertrand Maury, Delphine Salort. A 2-adic approach of the human respiratory tree. Networks and Heterogeneous Media, 2010, 5 (3) : 405-422. doi: 10.3934/nhm.2010.5.405

[3]

Vladimir Anashin, Andrei Khrennikov, Ekaterina Yurova. Ergodicity criteria for non-expanding transformations of 2-adic spheres. Discrete and Continuous Dynamical Systems, 2014, 34 (2) : 367-377. doi: 10.3934/dcds.2014.34.367

[4]

Huaning Liu, Xi Liu. On the correlation measures of orders $ 3 $ and $ 4 $ of binary sequence of period $ p^2 $ derived from Fermat quotients. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021008

[5]

Hua Liang, Jinquan Luo, Yuansheng Tang. On cross-correlation of a binary $m$-sequence of period $2^{2k}-1$ and its decimated sequences by $(2^{lk}+1)/(2^l+1)$. Advances in Mathematics of Communications, 2017, 11 (4) : 693-703. doi: 10.3934/amc.2017050

[6]

Vladimir Edemskiy, Sofia Koltsova. Estimate of 4-adic complexity of unified quaternary sequences of length $ 2p $. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022048

[7]

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

[8]

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

[9]

Yuhua Sun, Zilong Wang, Hui Li, Tongjiang Yan. The cross-correlation distribution of a $p$-ary $m$-sequence of period $p^{2k}-1$ and its decimated sequence by $\frac{(p^{k}+1)^{2}}{2(p^{e}+1)}$. Advances in Mathematics of Communications, 2013, 7 (4) : 409-424. doi: 10.3934/amc.2013.7.409

[10]

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

[11]

Kai-Uwe Schmidt, Jonathan Jedwab, Matthew G. Parker. Two binary sequence families with large merit factor. Advances in Mathematics of Communications, 2009, 3 (2) : 135-156. doi: 10.3934/amc.2009.3.135

[12]

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

[13]

Zilong Wang, Guang Gong. Correlation of binary sequence families derived from the multiplicative characters of finite fields. Advances in Mathematics of Communications, 2013, 7 (4) : 475-484. doi: 10.3934/amc.2013.7.475

[14]

Ji-Woong Jang, Young-Sik Kim, Sang-Hyo Kim. New design of quaternary LCZ and ZCZ sequence set from binary LCZ and ZCZ sequence set. Advances in Mathematics of Communications, 2009, 3 (2) : 115-124. doi: 10.3934/amc.2009.3.115

[15]

Ning Zhang. A symmetric Gauss-Seidel based method for a class of multi-period mean-variance portfolio selection problems. Journal of Industrial and Management Optimization, 2020, 16 (2) : 991-1008. doi: 10.3934/jimo.2018189

[16]

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

[17]

Xiaohui Liu, Jinhua Wang, Dianhua Wu. Two new classes of binary sequence pairs with three-level cross-correlation. Advances in Mathematics of Communications, 2015, 9 (1) : 117-128. doi: 10.3934/amc.2015.9.117

[18]

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

[19]

Jianlu Zhang. Coexistence of period 2 and 3 caustics for deformative nearly circular billiard maps. Discrete and Continuous Dynamical Systems, 2019, 39 (11) : 6419-6440. doi: 10.3934/dcds.2019278

[20]

Rohit Kumar, V.V.M.S. Chandramouli. Period tripling and quintupling renormalizations below $ C^2 $ space. Discrete and Continuous Dynamical Systems, 2021, 41 (12) : 5633-5658. doi: 10.3934/dcds.2021091

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (126)
  • HTML views (152)
  • Cited by (0)

Other articles
by authors

[Back to Top]