Article Contents
Article Contents

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

• * Corresponding author: Huaning Liu
• 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.

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

 Citation:

•  [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.