On the correlation measures of orders 3 and 4 of binary sequence of period p^2 derived from Fermat quotients

Previous Article
Classical reduction of gap SVP to LWE: A concrete security analysis
AMC Home
This Issue
Next Article
Extremal absorbing sets in low-density parity-check codes

doi: 10.3934/amc.2021008

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 correlation measures of orders $ 3 $ and $ 4 $ of binary sequence of period $ p^2 $ derived from Fermat quotients

Huaning Liu ^, and Xi Liu

Research Center for Number Theory and Its Applications, School of Mathematics, Northwest University, Xi'an 710127, China

^* Corresponding author: Huaning Liu

Received October 2020 Revised February 2021 Early access April 2021

Let

$ p $

be a prime and let

$ n $

be an integer with

$ (n, p) = 1 $

. The Fermat quotient

$ q_p(n) $

is defined as

$ q_p(n)\equiv \frac{n^{p-1}-1}{p} \ (\bmod\ p), \quad 0\leq q_p(n)\leq p-1. $

We also define

$ q_p(kp) = 0 $

for

$ k\in \mathbb{Z} $

. Chen, Ostafe and Winterhof constructed the binary sequence

$ E_{p^2} = \left(e_0, e_1, \cdots, e_{p^2-1}\right)\in \{0, 1\}^{p^2} $

as

$ \begin{equation*} \begin{split} e_{n} = \left\{\begin{array}{ll} 0, & \hbox{if }\ 0\leq \frac{q_p(n)}{p}<\frac{1}{2}, \\ 1, & \hbox{if }\ \frac{1}{2}\leq \frac{q_p(n)}{p}<1, \end{array} \right. \end{split} \end{equation*} $

and studied the well-distribution measure and correlation measure of order

$ 2 $

by using estimates for exponential sums of Fermat quotients. In this paper we further study the correlation measures of the sequence. Our results show that the correlation measure of order

$ 3 $

is quite good, but the

$ 4 $

-order correlation measure of the sequence is very large.

Keywords: Fermat quotient, binary sequence, correlation measure, exponential sum.

Mathematics Subject Classification: Primary: 11K45, 11B50; Secondary: 94A55, 94A60.

Citation: 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, doi: 10.3934/amc.2021008

References:

[1]	H. Aly and A. Winterhof, Boolean functions derived from Fermat quotients, Cryptogr. Commun., 3 (2011), 165-174. doi: 10.1007/s12095-011-0043-5.
[2]	M.-C. Chang, Short character sums with Fermat quotients, Acta Arith., 152 (2012), 23-38. doi: 10.4064/aa152-1-3.
[3]	Z. Chen, Trace representation and linear complexity of binary sequences derived from Fermat quotients, Sci. China Inf. Sci., 57 (2014), 112109, 10 pp. doi: 10.1007/s11432-014-5092-x.
[4]	Z. Chen and X. Du, On the linear complexity of binary threshold sequences derived from Fermat quotients, Des. Codes Cryptogr., 67 (2013), 317-323. doi: 10.1007/s10623-012-9608-3.
[5]	Z. Chen, L. Hu and X. Du, Linear complexity of some binary sequences derived from Fermat quotients, China Commun., 9 (2012), 105-108.
[6]	Z. Chen, A. Ostafe and A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients, In Arithmetic of Finite Fields, Lecture Notes in Computer Science 6087, Springer, Berlin, (2010), 73-85. doi: 10.1007/978-3-642-13797-6_6.
[7]	Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discr. Math., 28 (2014), 1-7. doi: 10.1137/130907951.
[8]	X. Du, A. Klapper and Z. Chen, Linear complexity of pseudorandom sequences generated by Fermat quotients and their generalizations, Inform. Process. Lett., 112 (2012), 233-237. doi: 10.1016/j.ipl.2011.11.017.
[9]	D. Gomez and A. Winterhof, Multiplicative character sums of Fermat quotients and pseudorandom sequences, Period. Math. Hungar., 64 (2012), 161-168. doi: 10.1007/s10998-012-3747-1.
[10]	D. R. Heath-Brown, An estimate for Heilbronn's exponential sum, In Analytic Number Theory, Proceedings of a Conference in Honor of Heini Halberstam, Progr. Math., Birkhäuser, Boston, 139 (1996), 451-463.
[11]	C. Mauduit and A. Sárközy, On finite pseudorandom binary sequencs I: Measure of pseudorandomness, the Legendre symbol, Acta Arith., 82 (1997), 365-377. doi: 10.4064/aa-82-4-365-377.
[12]	A. Ostafe and I. E. Shparlinski, Pseudorandomness and dynamics of Fermat quotients, SIAM J. Discr. Math., 25 (2011), 50-71. doi: 10.1137/100798466.
[13]	I. E. Shparlinskii, Fermat quotients: Exponential sums, value set and primitive roots, Bull. Lond. Math. Soc., 43 (2011), 1228-1238. doi: 10.1112/blms/bdr058.
[14]	I. E. Shparlinski, Character sums with Fermat quotients, Quart. J. Math., 62 (2011), 1031-1043. doi: 10.1093/qmath/haq028.
[15]	I. E. Shparlinski, Bounds of multiplicative character sums with Fermat quotients of primes, Bull. Aust. Math. Soc., 83 (2011), 456-462. doi: 10.1017/S000497271000198X.

show all references

References:

[1]	H. Aly and A. Winterhof, Boolean functions derived from Fermat quotients, Cryptogr. Commun., 3 (2011), 165-174. doi: 10.1007/s12095-011-0043-5.
[2]	M.-C. Chang, Short character sums with Fermat quotients, Acta Arith., 152 (2012), 23-38. doi: 10.4064/aa152-1-3.
[3]	Z. Chen, Trace representation and linear complexity of binary sequences derived from Fermat quotients, Sci. China Inf. Sci., 57 (2014), 112109, 10 pp. doi: 10.1007/s11432-014-5092-x.
[4]	Z. Chen and X. Du, On the linear complexity of binary threshold sequences derived from Fermat quotients, Des. Codes Cryptogr., 67 (2013), 317-323. doi: 10.1007/s10623-012-9608-3.
[5]	Z. Chen, L. Hu and X. Du, Linear complexity of some binary sequences derived from Fermat quotients, China Commun., 9 (2012), 105-108.
[6]	Z. Chen, A. Ostafe and A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients, In Arithmetic of Finite Fields, Lecture Notes in Computer Science 6087, Springer, Berlin, (2010), 73-85. doi: 10.1007/978-3-642-13797-6_6.
[7]	Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discr. Math., 28 (2014), 1-7. doi: 10.1137/130907951.
[8]	X. Du, A. Klapper and Z. Chen, Linear complexity of pseudorandom sequences generated by Fermat quotients and their generalizations, Inform. Process. Lett., 112 (2012), 233-237. doi: 10.1016/j.ipl.2011.11.017.
[9]	D. Gomez and A. Winterhof, Multiplicative character sums of Fermat quotients and pseudorandom sequences, Period. Math. Hungar., 64 (2012), 161-168. doi: 10.1007/s10998-012-3747-1.
[10]	D. R. Heath-Brown, An estimate for Heilbronn's exponential sum, In Analytic Number Theory, Proceedings of a Conference in Honor of Heini Halberstam, Progr. Math., Birkhäuser, Boston, 139 (1996), 451-463.
[11]	C. Mauduit and A. Sárközy, On finite pseudorandom binary sequencs I: Measure of pseudorandomness, the Legendre symbol, Acta Arith., 82 (1997), 365-377. doi: 10.4064/aa-82-4-365-377.
[12]	A. Ostafe and I. E. Shparlinski, Pseudorandomness and dynamics of Fermat quotients, SIAM J. Discr. Math., 25 (2011), 50-71. doi: 10.1137/100798466.
[13]	I. E. Shparlinskii, Fermat quotients: Exponential sums, value set and primitive roots, Bull. Lond. Math. Soc., 43 (2011), 1228-1238. doi: 10.1112/blms/bdr058.
[14]	I. E. Shparlinski, Character sums with Fermat quotients, Quart. J. Math., 62 (2011), 1031-1043. doi: 10.1093/qmath/haq028.
[15]	I. E. Shparlinski, Bounds of multiplicative character sums with Fermat quotients of primes, Bull. Aust. Math. Soc., 83 (2011), 456-462. doi: 10.1017/S000497271000198X.

[1]	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
[2]	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
[3]	Xiaoni Du, Chenhuang Wu, Wanyin Wei. An extension of binary threshold sequences from Fermat quotients. Advances in Mathematics of Communications, 2016, 10 (4) : 743-752. doi: 10.3934/amc.2016038
[4]	Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1795-1807. doi: 10.3934/jimo.2021044
[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]	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
[7]	Aixian Zhang, Zhengchun Zhou, Keqin Feng. A lower bound on the average Hamming correlation of frequency-hopping sequence sets. Advances in Mathematics of Communications, 2015, 9 (1) : 55-62. doi: 10.3934/amc.2015.9.55
[8]	Hua Liang, Wenbing Chen, Jinquan Luo, Yuansheng Tang. A new nonbinary sequence family with low correlation and large size. Advances in Mathematics of Communications, 2017, 11 (4) : 671-691. doi: 10.3934/amc.2017049
[9]	Ferruh Özbudak, Eda Tekin. Correlation distribution of a sequence family generalizing some sequences of Trachtenberg. Advances in Mathematics of Communications, 2021, 15 (4) : 647-662. doi: 10.3934/amc.2020087
[10]	Wenbing Chen, Jinquan Luo, Yuansheng Tang, Quanquan Liu. Some new results on cross correlation of $p$-ary $m$-sequence and its decimated sequence. Advances in Mathematics of Communications, 2015, 9 (3) : 375-390. doi: 10.3934/amc.2015.9.375
[11]	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
[12]	Guangmei Shao, Wei Xue, Gaohang Yu, Xiao Zheng. Improved SVRG for finite sum structure optimization with application to binary classification. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2253-2266. doi: 10.3934/jimo.2019052
[13]	Marc Kessböhmer, Bernd O. Stratmann. On the asymptotic behaviour of the Lebesgue measure of sum-level sets for continued fractions. Discrete and Continuous Dynamical Systems, 2012, 32 (7) : 2437-2451. doi: 10.3934/dcds.2012.32.2437
[14]	Zhenyu Zhang, Lijia Ge, Fanxin Zeng, Guixin Xuan. Zero correlation zone sequence set with inter-group orthogonal and inter-subgroup complementary properties. Advances in Mathematics of Communications, 2015, 9 (1) : 9-21. doi: 10.3934/amc.2015.9.9
[15]	Limengnan Zhou, Daiyuan Peng, Hongyu Han, Hongbin Liang, Zheng Ma. Construction of optimal low-hit-zone frequency hopping sequence sets under periodic partial Hamming correlation. Advances in Mathematics of Communications, 2018, 12 (1) : 67-79. doi: 10.3934/amc.2018004
[16]	Valery Y. Glizer, Oleg Kelis. Singular infinite horizon zero-sum linear-quadratic differential game: Saddle-point equilibrium sequence. Numerical Algebra, Control and Optimization, 2017, 7 (1) : 1-20. doi: 10.3934/naco.2017001
[17]	Yuk L. Yung, Cameron Taketa, Ross Cheung, Run-Lie Shia. Infinite sum of the product of exponential and logarithmic functions, its analytic continuation, and application. Discrete and Continuous Dynamical Systems - B, 2010, 13 (1) : 229-248. doi: 10.3934/dcdsb.2010.13.229
[18]	Nam Yul Yu. A Fourier transform approach for improving the Levenshtein's lower bound on aperiodic correlation of binary sequences. Advances in Mathematics of Communications, 2014, 8 (2) : 209-222. doi: 10.3934/amc.2014.8.209
[19]	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
[20]	Mark F. Demers. Uniqueness and exponential mixing for the measure of maximal entropy for piecewise hyperbolic maps. Discrete and Continuous Dynamical Systems, 2021, 41 (1) : 217-256. doi: 10.3934/dcds.2020217

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Huaning Liu Xi Liu
on Google Scholar
Huaning Liu Xi Liu

2020 Impact Factor: 0.935

Tools

Article outline

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Huaning Liu Xi Liu
on Google Scholar
Huaning Liu Xi Liu

[Back to Top]