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

For a prime \(p\) and an integer \(n\) with \(\gcd(n,p)=1\) the Fermat quotient \(q_p(n)\) is defined by \[ q_p(n)=\frac{n^{p-1}-1}{p}\bmod p \] and \(q_p(n)=0\) otherwise. \textit{Z. Chen} et al. [Lect. Notes Comput. Sci. 6087, 73--85 (2010; Zbl 1230.11092)] studied the binary sequence \((e_0,e_1,\ldots,e_{p^2-1})\) defined by \[ e_n=\left\{\begin{array}{cc} 0 & \mbox{if }0\le q_p(n)<p/2,\\ 1 &\mbox{if }p/2 \le q_p(n)<1,\end{array}\right. \quad n=0,1,\ldots,p^2-1. \] In particular, they showed that the correlation measure of order \(2\) of this sequence is of order of magnitude at most \(p (\log p)^3\) which is a desirable feature of pseudorandomness. In this paper the authors continue their investigations. First they show that the correlation measure of order \(3\) is also of desirable order of magnitude at most \(p (\log p)^4\). Then they show that the correlation measure of order \(4\) is of order of magnitude \(p^2\) which is undesirable. Consequently, this sequence is not pseudorandom and, in particular, not suitable in cryptography.