On the <i>p</i>-Adic Complexity of the Ding-Helleseth-Martinsen Binary Sequences

JING Xiaoyan; XU Zhefeng; YANG Minghui; FENG Keqin

doi:10.1049/cje.2020.08.016

Volume 30 Issue 1

Jan. 2021

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2021 > 30(1): 64-71

JING Xiaoyan, XU Zhefeng, YANG Minghui, et al., “On the p-Adic Complexity of the Ding-Helleseth-Martinsen Binary Sequences,” Chinese Journal of Electronics, vol. 30, no. 1, pp. 64-71, 2021, doi: 10.1049/cje.2020.08.016

Citation:

JING Xiaoyan, XU Zhefeng, YANG Minghui, et al., “On the p-Adic Complexity of the Ding-Helleseth-Martinsen Binary Sequences,” Chinese Journal of Electronics, vol. 30, no. 1, pp. 64-71, 2021, doi: 10.1049/cje.2020.08.016

Citation:

PDF( 444 KB)

On the p-Adic Complexity of the Ding-Helleseth-Martinsen Binary Sequences

doi: 10.1049/cje.2020.08.016

1.
Research Center for Number Theory and Its Applications, Northwest University, Xi'an 710127, China
2.
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
3.
Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China

Funds:

the National Natural Science Foundation of China (NSFC) 11701553

the National Natural Science Foundation of China (NSFC) 11571007

the National Natural Science Foundation of China (NSFC) 11971381

the National Natural Science Foundation of China (NSFC) 11701447

Natural Science Foundation of Shaanxi Province, China 2014JM1001

Natural Science Foundation of Shaanxi Province, China 2015KJXX-27

More Information

Author Bio:
JING Xiaoyan   was born in 1995. She received the B.E. degree in telecommunication engineering from Xidian University, Xi'an, China. She is currently working toward the M.S. degree at the School of Mathematics, Northwest University, Xi'an, China. Her research interests include coding theory and sequences. (Email: jxymg@126.com)

XU Zhefeng   received the B.E., Ph.D. degrees from Northwest University, Xi'an, China in 2002 and 2007 respectively. He was a postdoctoral researcher in Xi'an Jiaotong University from January 2008 to March 2011. He is a doctoral supervisor and professor in the Research Center for Number Theory and Its Applications, Northwest University, Xi'an, China. His research interests include number theory and its applications. (Email: zfxu@nwu.edu.cn)

FENG Keqin   received the M.S. degree from the University of Science and Technology of China (USTC), Beijing, in 1968. Since 1973, he has been with the Department of Mathematics, USTC, and then with the State Key Laboratory of Information Safety of USTC, Beijing, China. Currently, he is with the Department of Mathematical Sciences, Tsinghua University, Beijing. His current research interests are coding theory, cryptography, and algebraic number theory. (Email: fengkq@mail.tsinghua.edu.cn)
Corresponding author: YANG Minghui (corresponding author) received the M.S. degree in mathematics from Hefei University of Technology, Hefei, China, in 2010 and the Ph.D. degree in computer and information from Hefei University of Technology, Hefei, China, in 2013. She was a postdoctoral researcher in the Institute of Information Engineering, Chinese Academy of Sciences, from July 2013 to July 2015. She is currently an assistant researcher in the Institute of Information Engineering, Chinese Academy of Sciences. Her research interests include coding theory and sequences. (Email: yangminghui6688@163.com)
Received Date: 2020-04-06
Accepted Date: 2020-06-10
Publish Date: 2021-01-01

Abstract

Abstract

The purpose of this paper is to determine the $p$-adic complexity of the Ding-Helleseth-Martinsen (DHM) sequences with period $N=2q$, where $q \equiv 5\pmod 8$ is a prime number. We firstly use the $p$-adic exponential valuation, cyclotomic numbers of order four, "Gauss periods" and "quadratic Gauss sums" on finite field $\mathbb{F_q}$ and valued in $\mathbb{Z_{p.N-1}}$ to determine the $p$-adic complexity of the DHM sequences.

FullText(HTML)

References(19)

References

[1]	A. Klapper and M. Goresky, "Feedback shift registers, 2-adic span, and combiners with memory", J. Cryptol. , Vol. 10, No. 2, pp. 111-147, 1997. doi: 10.1007/s001459900024
[2]	A. Klapper and M. Goresky, "Cryptanalysis based on 2-adic rational approximation", in: D. Coppersmith (Ed. ), Advances in Cryptology - Crypto 95, Lecture Notes in Computer Science, Springer, Heidelberg, Vol. 963, pp. 262-273, 1995.
[3]	R. Hofer and A. Winterhof, "On the 2-adic complexity of the two-prime generator", IEEE Trans. Inf. Theory, Vol. 64, No. 8, pp. 5957-5960, 2018. doi: 10.1109/TIT.2018.2811507
[4]	H. Hu, "Comments on a new method to compute the 2-adic complexity of binary sequences", IEEE Trans. Inf. Theory, Vol. 64, No. 4, pp. 5803-5804, 2014. http://ieeexplore.ieee.org/document/6736120/
[5]	Y. Sun, Q. Wang and T. Yan, "A lower bound on the 2-adic complexity of modified Jacobi Sequences", Cryptogr. Commun. , Vol. 11, No. 2, pp. 337-349, 2019. doi: 10.1007/s12095-018-0300-y
[6]	Y. Sun, Q. Wang and T. Yan, "The exact autocorrelation distribution and 2-adic complexity of a class of binary sequences with almost optimal autocorrelation", Cryptogr. Commun. , Vol. 10, No. 3, pp. 67-477, 2018. doi: 10.1007/s12095-017-0233-x
[7]	Y. Sun, T. Yan, L. Wang and Z. Chen, "The 2-adic compelxity of a class of binary sequences with optimal autocorrealtion magnitude", Cryptogr. Commun. , DOI10.1007/s12095-0190-00411-4, 2019. doi: 10.1007/s12095-017-0233-x
[8]	T. Tian and W. Qi, "2-adic complexity of binary $ m $-sequences", IEEE Trans. Inform. Theory, Vol. 56, No. 1, pp. 450-454, 2010. doi: 10.1109/TIT.2009.2034904
[9]	Z. Xiao, X. Zeng and Z. Sun, "2-adic complexity of two classes of generalized cyclotomic binary sequences", Int. J. Found. Comput. Sci. , Vol. 27, No. 7, pp. 879-893, 2016. doi: 10.1142/S0129054116500350
[10]	H. Xiong, L. Qu and C. Li, "A new method to compute the 2-adic complexity of binary sequecnes", IEEE Trans. Inform. Theory, Vol. 60, No. 4, pp. 2399-2406, 2014. doi: 10.1109/TIT.2014.2304451
[11]	H. Xiong, L. Qu and C. Li, "2-adic complexity of binary sequences with interleaved strcture", Finite Fields Appl. , Vol. 33, pp. 14-28, 2015. doi: 10.1016/j.ffa.2014.09.009
[12]	M. Yang, L. Zhang and K. Feng, "On the 2-adic complexity of a class of binary sequences of period $ 4p $ with optimal autocorrelation magnitude", IEEE Int. Symp. Inf. Theory, Los Angeles, USA, arXiv: 1904.13012, 2020.
[13]	L. Zhang, J. Zhang, M. Yang and K. Feng, "On the 2-adic complexity of the Ding-Helleseth-Martinsen binary sequecnes", IEEE Trans. Inf. Theory, Vol. 66, No. 7, pp. 4613-4620, 2020. doi: 10.1109/TIT.2020.2964171
[14]	A. Klapper, "A survey of feedback with carry shift registers", SETA 2004, T. Helleseth et al. (Eds), LNCS 3486, pp. 56-71, 2005.
[15]	C. Ding, T. Helleseth and H. Martinsen, "New families of binary sequences with optimal three-level autocorrelation", IEEE Trans. Inf. Theory, Vol. 47, No. 1, pp. 428-433, 2001. doi: 10.1109/18.904555
[16]	B. Berndt, R. Evans and K. Williams, Gauss and Jacobi Sums, John Wiley and Sons INC, 1998.
[17]	T. Storer, Cyclotomy and Difference Sets, Markham, Chicago, 1967.
[18]	J. Zhang and C. Zhao, "The linear complexity of a class of binary sequences with period $ 2p $", Algebra Eng. Commun. Comput. , Vol. 26, pp. 475-491, 2015. doi: 10.1007/s00200-015-0261-8
[19]	V. Edemskiy and A. Palvinskiy, "The linear complexity of binary sequences of length $ 2p $ with optimal three-level autocorrelation", Inf. Process. Lett. , Vol. 116, pp. 153-156, 2016. doi: 10.1016/j.ipl.2015.09.007