A result on the distribution of quadratic residues with applications to elliptic curve cryptography

Abstract

In this paper, we prove that for any polynomial function f of fixed degree without multiple roots, the probability that all the (f(x + 1), f(x + 2), ..., f(x +κ)) are quadratic non-residue is ≈ 1/2^κ. In particular for f(x) = x³ + ax + b corresponding to the elliptic curve y² = x³ + ax + b, it implies that the quadratic residues (f(x + 1), f(x + 2), . . . in a finite field are sufficiently randomly distributed. Using this result we describe an efficient implementation of El-Gamal Cryptosystem. that requires efficient computation of a mapping between plain-texts and the points on the elliptic curve.