Remarks on pseudorandom binary sequences over elliptic curves
type: Item
instance of: scholarly article
zbMATH Open document ID: 1262.11077
author: László Mérai
publication date: 2012-05-11T00:00:00Z
full work available at URL: fulltext.html
Mathematics Subject Classification ID: 11K06
Mathematics Subject Classification ID: 65C10
Mathematics Subject Classification ID: 11K36
Mathematics Subject Classification ID: 11K38
Mathematics Subject Classification ID: 11K45
zbMATH DE Number: 6033529
zbMATH Keywords: binary sequences
zbMATH Keywords: pseudorandomness
zbMATH Keywords: elliptic curve
zbMATH Keywords: character
zbMATH Keywords: discrepancy
zbMATH Keywords: well-distribution measure
zbMATH Keywords: correlation measure of order l
MaRDI profile type: Publication
title: Remarks on pseudorandom binary sequences over elliptic curves
published in: Fundamenta Informaticae
review text: 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 …
reviewed by: Vassil Grozdanov
description: scientific article; zbMATH DE number 6033529