American Institute of Mathematical Sciences

Advanced
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.  Google Scholar

[2]

M.-C. Chang, Short character sums with Fermat quotients, Acta Arith., 152 (2012), 23-38.  doi: 10.4064/aa152-1-3.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

Z. Chen, L. Hu and X. Du, Linear complexity of some binary sequences derived from Fermat quotients, China Commun., 9 (2012), 105-108.   Google Scholar

[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.  Google Scholar

[7]

Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discr. Math., 28 (2014), 1-7.  doi: 10.1137/130907951.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

I. E. Shparlinski, Character sums with Fermat quotients, Quart. J. Math., 62 (2011), 1031-1043.  doi: 10.1093/qmath/haq028.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[2]

M.-C. Chang, Short character sums with Fermat quotients, Acta Arith., 152 (2012), 23-38.  doi: 10.4064/aa152-1-3.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

Z. Chen, L. Hu and X. Du, Linear complexity of some binary sequences derived from Fermat quotients, China Commun., 9 (2012), 105-108.   Google Scholar

[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.  Google Scholar

[7]

Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discr. Math., 28 (2014), 1-7.  doi: 10.1137/130907951.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

I. E. Shparlinski, Character sums with Fermat quotients, Quart. J. Math., 62 (2011), 1031-1043.  doi: 10.1093/qmath/haq028.  Google Scholar

[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.  Google Scholar

[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 & Management Optimization, 2021  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]

Guangmei Shao, Wei Xue, Gaohang Yu, Xiao Zheng. Improved SVRG for finite sum structure optimization with application to binary classification. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2253-2266. doi: 10.3934/jimo.2019052
[12]

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
[13]

Marc Kessböhmer, Bernd O. Stratmann. On the asymptotic behaviour of the Lebesgue measure of sum-level sets for continued fractions. Discrete & 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 & 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 & 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 & Continuous Dynamical Systems, 2021, 41 (1) : 217-256. doi: 10.3934/dcds.2020217

2020 Impact Factor: 0.935

Tools

Article outline

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences