    doi: 10.3934/amc.2021008

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

 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.
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:
  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  M.-C. Chang, Short character sums with Fermat quotients, Acta Arith., 152 (2012), 23-38.  doi: 10.4064/aa152-1-3.  Google Scholar  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  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  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  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  Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discr. Math., 28 (2014), 1-7.  doi: 10.1137/130907951.  Google Scholar  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  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  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  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  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  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  I. E. Shparlinski, Character sums with Fermat quotients, Quart. J. Math., 62 (2011), 1031-1043.  doi: 10.1093/qmath/haq028.  Google Scholar  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:
  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  M.-C. Chang, Short character sums with Fermat quotients, Acta Arith., 152 (2012), 23-38.  doi: 10.4064/aa152-1-3.  Google Scholar  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  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  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  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  Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discr. Math., 28 (2014), 1-7.  doi: 10.1137/130907951.  Google Scholar  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  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  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  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  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  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  I. E. Shparlinski, Character sums with Fermat quotients, Quart. J. Math., 62 (2011), 1031-1043.  doi: 10.1093/qmath/haq028.  Google Scholar  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
  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  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  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  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  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  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  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  Ferruh Özbudak, Eda Tekin. Correlation distribution of a sequence family generalizing some sequences of Trachtenberg. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020087  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  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  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  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  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  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  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  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  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  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  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  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