Remarks on pseudorandom binary sequences over elliptic curves (Q2883173)

The pseudorandom binary sequences are important objects, which have many applications in different branches of the science. The numerical measures for the pseudorandomness of the binary sequences show the quality of these sequences. These measures are a tool for a classification of the binary sequences with respect to the good pseudorandom properties, that they have.NEWLINENEWLINEIn the present paper the pseudorandomness of binary sequences, defined over elliptic curves, is studied and both the well-distribution measure and the correlation measure of order \(l\) are estimated.NEWLINENEWLINEFor a prime number \(p>3,\) the elliptic curve \(y^2 = x^3 + Ax + B\) over the field \(\mathbb F_p,\) is used to construct binary sequences. The elliptic curve congruential generator is defined by the relation \(P_n = G \oplus P_{n-1}= nG \oplus P_0,\) with the initial value \(P_0.\) An arbitrary non-constant rational function \(f \in\mathbb F_p({\mathcal E})\) is used to construct the sequence \(s_n = f(P_n)\).NEWLINENEWLINENEWLINEIn Section 2, by using the Kohel-Shparlinski bound, the one-dimensional exponential sum with respect to the function \(f\) is estimated. Then the Erdős-Turán-Koksma inequality is used to obtain an estimation of the discrepancy of a special class of sequences. In Lemma 2.1 an estimation of the one-dimensional exponential sum with respect to a non-constant rational function \(f\) is presented. In Theorem 2.1 an estimation of the multidimensional exponential sum with respect to the function \(f\) is given. This estimation permits to obtain an order \(\log T,\) where \(T\) is the order of the point \(G \in {\mathcal E}(\mathbb F_p),\) of the exponential sum. To prove Theorem 2.1, the estimation of one dimensional exponential sum obtained in Lemma 2.1, is essentially used. The result of Theorem 2.1 and the Erdős-Turán-Koksma inequality are used, to obtain a bound of the discrepancy of the sequence \(\Gamma({\mathbf d},N,l),\) constructed in explicit form in the paper. To the end of Section 2 Theorem 2.1 is proved.NEWLINENEWLINENEWLINEIn Section 3, in order to study the pseudorandomness of binary sequences, the well-distribution measure \(W(E_N)\) and the correlation measure of order \(l\) \(C_l(E_N)\) are studied. The pseudorandom measures of the binary sequence \(E_N = \{e_1, e_2, \ldots, e_N\}\) has already been studied in some special choice of the function \(f.\) Here the obtained results are true for an arbitrary non-constant rational function \(f\). In Theorem 3.1 an estimation of the well-distribution measure \(W(E_T)\) of the binary sequences \(E_T\) is obtained. By using the result of Theorem 3.1, as a consequence, the order \(\log T\) of the discrepancy of the sequence \(\Gamma(T)\) is obtained. In Theorem 3.2 an estimation of the correlation measure of order \(l\) \(C_l(E_T)\) of the binary sequence \(E_T\) is obtained. Section 3 ends with the proof of Theorem 3.2.