Pseudorandom sequences from

elliptic curves

Summary. In this chapter some known constructions to produce pseudorandom

sequences with the aid of elliptic curves will be generalized. Both additive and

multiplicative characters on elliptic curves will be used for this purpose. This chapter

is based on joint work with Peter Beelen [BD02].

5.1 Introduction

Nowadays, many applications call for random numbers. One of the most prefer-

able ways to generate those would be to take a monkey, give him a coin to ¬‚ip, and

write down the result of each coin ¬‚ip. Unfortunately this process is quite slow,

and a faster way to generate random numbers is needed. On second thought, a

sequence of numbers that appears random would be just as good - who could tell

the di¬erence? Such a sequence will be called pseudorandom.

Many people have constructed pseudorandom number generators using many,

diverse methods (see for example [MOV97, Chapter 5] for an overview). The ¬rst

study of using linear congruences on elliptic curves to generate pseudorandom se-

quences was done in [Hal94]. Further results on these generators were obtained in

[MS02; GBS00; KS00; VW00]. Some of these constructions will be generalized here

and another construction using linear recurrence relations on elliptic curves will be

introduced. An instance of this last construction was investigated in [GL02].

5.2 Some properties of elliptic curves

As elliptic curves will be used heavily throughout this chapter, ¬rst some notation

will be ¬xed and some elementary properties of elliptic curves will be stated. The

algebraic closure of a ¬eld F will be denoted by F .

De¬nition 5.2.1 An elliptic curve E is the set of projective points in P2 satisfying

49

50 Pseudorandom sequences from elliptic curves

the Weierstrass equation F (X, Y, Z) = 0, where F is de¬ned as

F (X, Y, Z) = Y 2 Z + a1 XY Z + a3 Y Z 2 ’ X 3 ’ a2 X 2 Z ’ a4 XZ 2 ’ a6 Z 3 .

A curve E is said to be de¬ned over Fq if a1 , . . . , a6 ∈ Fq .

However, usually one considers the (a¬ne) non-homogeneous equation obtained by

putting x = X/Z and y = Y /Z in the equation F (X, Y, Z) = 0:

y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 ,

always remembering to include the point O at in¬nity, which has projective coordi-

nates [0 : 1 : 0]. We will write the a¬ne equation as f (x, y) = F (X/Z, Y /Z, 1). A

point P satisfying ‚f (P ) = ‚f (P ) = 0, will be called singular. In this chapter, we

‚x ‚y

will only consider non-singular elliptic curves, that is elliptic curves which have no

singular point(s).

Elliptic curves have an Abelian group structure [Sil86, Section 3.2]. Adding two

points P and Q is done by ¬rst taking the line through P and Q (if P = Q, take the

tangent at P ). This line will intersect the curve E in a third point R, since f is a

cubic equation. Note that points are counted with multiplicity. The sum of P and

Q is now de¬ned to be the intersection point of the line through R and O. Scalar

multiplication of a point P on an elliptic curve by n, i.e. adding P to itself n times,

will be denoted by [n]P .

A point is called F-rational if its coordinates are in F. The group of F-rational

points (see [Sil86, page 57] for proof that these points form a group) on the curve

E will be denoted by E(F). A point P ∈ E is called a n-torsion point if it satis¬es

[n]P = O. The n-torsion subgroup of E will be denoted by E[n].

The function ¬eld of an elliptic curve E de¬ned over Fq is de¬ned to be the

quotient ¬eld of Fq [x, y]/(f (x, y)). It will be denoted by F(C), or by Fq (C) if only

the functions with coe¬cients in Fq are considered. The valuation map vP (g) is a

map from F(C) to Z ∪ ∞, which takes as value minus the pole order of g at P . So if

g has a zero of degree k at point P and a pole of degree l at Q, one has vP (g) = k

and vQ (g) = ’l. For every (rational) function f ∈ F(C), there are ¬nitely many

points where vP (f ) = 0 [Sil86, Proposition 2.1.2].

An algebraic curve C is a projective variety of dimension 1, with an arbitrary

genus g. Elliptic curves are algebraic curves with genus g = 1. For more information

on algebraic curves, see for instance [Sil86, Chapter 2] or [Sti93].

The following famous result by Hasse and Weil concerns the number of points

of an algebraic curve. For a proof of this theorem, see for instance [Sti93, Section

5.2].

Theorem 5.2.2 (Hasse-Weil bound) Let C be an algebraic curve de¬ned over

√

Fq of genus g. Then there exist ±1 , . . . , ±g ∈ C of length q, such that for all e ∈ N

g

e

(±i + ±e ) .

e

#C(Fqe ) = q + 1 ’ i

i=1

5.3 Pseudorandom sequences 51

Corollary 5.2.3 The number of points of an algebraic curve C de¬ned over Fq of

genus g satis¬es √

|#C(Fqe ) ’ q e ’ 1| ¤ 2g q e .

Proof: This follows easily from Theorem 5.2.2.

In the case of an elliptic curve, we have

Corollary 5.2.4 The number of points of an elliptic curve E de¬ned over Fq sat-

is¬es √

|#C(Fqe ) ’ q e ’ 1| ¤ 2 q e .

Proof: This follows easily from Theorem 5.2.2 and the fact that the genus of an

elliptic curve is 1.

For the following proposition, see [Sil86, page 145].

Proposition 5.2.5 Let E be an elliptic curve de¬ned over the ¬nite ¬eld Fq . Then

there exist numbers k and l such that the elliptic curve as an Abelian group satis¬es

E(Fq ) ∼ Z/kZ — Z/klZ.

=

Furthermore, k divides (q ’ 1).

The k and l from the above proposition will be denoted by k(E) and l(E) respectively

or by k(E, Fq ) and l(E, Fq ) if the ¬eld of de¬nition is not immediately clear. Note

that if k = 1, the elliptic curve will have a cyclic structure.

Since k = k(E, Fq ) divides q ’ 1, the map from E to E obtained by multiplying

with k, is of degree k 2 and unrami¬ed, i.e. the equation [k]P = Q has k solutions

for any point Q. Further note that E[k] ‚ E(Fq ).

5.3 Pseudorandom sequences

In this section some basic de¬nitions concerning pseudorandom sequences are

given. First a very handy tool is introduced:

De¬nition 5.3.1 The trace map TrFqe |Fq is a function from Fqe to Fq de¬ned by

2 e’1

TrFqe |Fq (x) = x + xq + xq + · · · + xq .

Note that the trace map is Fq “linear, since (a+b)q = aq +bq in Fqe , and (±a)q = ±aq

for ± ∈ Fq and a ∈ Fqe .

Now, some basic properties concerning pseudorandom sequences are discussed.

De¬nition 5.3.2 Let S = {s(0), s(1), . . . , s(N ’ 1)} be a sequence of elements of

Fq and let ± ∈ F— . Denote the characteristic of Fq by p. The balance of S with

q

respect to ± is de¬ned in the following way:

52 Pseudorandom sequences from elliptic curves

N ’1

1 TrFq |Fp (±s(i))

BS (±) = ζp ,

N i=0

where ζp is the pth root of unity exp(2πi/p). Furthermore, the balance of S is de¬ned

as

BS = max{|BS (±)|}.

—±∈Fq