Note that for binary sequences, this de¬nition is equivalent to

N ’1

1 1

(’1)s(i) = #{i : s(i) = 0} ’ #{i : s(i) = 1} .

BS =

N N

i=0

Thus the balance is a measure of any bias in the sequence S. Also, if s(i) takes

every value in Fq equally often, then BS = BS (±) = 0 for any ±.

Now a similar concept for sequences de¬ned over Z/mZ is introduced. It will be

assumed that m divides q’1. Then it is possible to identify Z/mZ with (F— )(q’1)/m .

q

—

Thus there exists a surjective homomorphism of groups χm : Fq ’ Z/mZ.

De¬nition 5.3.3 If S = {s(0), s(1), . . . , s(N ’ 1)} is a sequence of elements of

(F— )(q’1)/m , then the balance with respect to ± is de¬ned as

q

N ’1

1

ζmm (±s(i)) ,

χ

BS (±) =

N i=0

with ± ∈ F— and ζm = exp(2πi/m).

q

Now the autocorrelation of a sequence can be de¬ned in s similar way.

De¬nition 5.3.4 Let {s(0), s(1), . . . , s(N ’ 1)} be a sequence S of period N de¬ned

over the ¬nite ¬eld Fq . Write p for the characteristic of this ¬eld. Furthermore, let

±, β ∈ F— .

q

The autocorrelation of S with respect to ± and β is de¬ned as:

N ’1

1 TrFq |Fp (±s(i+d)’βs(i))

CS (d, ±, β) = ζp ,

N i=0

with 0 ¤ d < N and ζp = exp(2πi/p). For a sequence S de¬ned over (F— )(q’1)/m

q

the de¬nition is

N ’1

1

ζmm (±s(i+d)’βs(i)) ,

χ

CS (d, ±, β) =

N i=0

with ζm = exp(2πi/m).

5.4 Using additive characters 53

Note that in the above de¬nition i + d should be read modulo N . Also note that

for binary sequences this de¬nition amounts to

N ’1

1

(’1)s(i+d)+s(i) ,

CS (d) =

N i=0

which is the usual de¬nition of the autocorrelation (see for example [MOV97, Section

5.4]).

Another useful object is the crosscorrelation of two sequences:

De¬nition 5.3.5 Let S = {s(i)} and T = {t(i)} be two sequences de¬ned over Fq

having the same period N . Denote the characteristic of Fq by p and let ±, β ∈ F— .

q

The crosscorrelation of S and T with respect to ± and β is de¬ned as

N ’1

1 TrFq |Fp (±s(i+d)’βt(i))

CS,T (d, ±, β) = ζp ,

N i=0

with ζp = exp(2πi/p) and 0 ¤ d < N . For sequences S and T de¬ned over

(F— )(q’1)/m the crosscorrelation is de¬ned as

q

N ’1

1

ζmm (±s(i+d)’βt(i)) ,

χ

CS,T (d, ±, β) =

N i=0

with ζm = exp(2πi/m).

Note that the crosscorrelation CS,S (d, ±, β) of a sequence with itself is equal to

the autocorrelation CS (d, ±, β), as it should be.

The problem is to ¬nd a family of sequences Σ = {Si |i ∈ I} such that for all

i, j ∈ I the crosscorrelations CSi ,Sj (d, ±, β) are small. Such a family of sequences

could be used for CDMA purposes, for instance in mobile telephony. Also, the

autocorrelation of a sequence obtained by concatenating two or more sequences

from such a family is essentially bounded by these crosscorrelations. When the

generator has to switch to another member of the family, one would still want

certain properties to hold for the autocorrelation of its combined output.

5.4 Using additive characters

Some generalizations of known constructions of pseudorandom sequences from

elliptic curves will be given in this section.

Let E be an elliptic curve de¬ned over a ¬nite ¬eld Fqe of characteristic p. Sup-

pose for now that this group is cyclic of order N = l(E) (i.e. k(E) = 1) and has

generator P . Let f ∈ Fqe (E) be a function on E de¬ned over Fqe . The pseudoran-

dom sequence S = {s(i)} will be studied in this section, where the s(i) are given

by:

54 Pseudorandom sequences from elliptic curves

s(i) = TrFqe |Fq (f ([i]P )),

with 0 ¤ i < N .

The condition that E(Fqe ) is a cyclic group is a natural one, since an ordering

of the points in E(Fqe ) is needed. In the literature this assumption is often made.

Moreover, the ¬eld Fq is usually assumed to be Fp . Both these restrictions will be

removed in this section. First some concepts are introduced.

De¬nition 5.4.1 Let C be an algebraic curve of genus g de¬ned over Fq . Let f ∈

Fq (C) be a rational function on C de¬ned over Fq as well. De¬ne C AS (f, Fq ) to be

the set of all Fq -rational points Q on C such that there exists a function g ∈ Fq (C)

(depending on Q) with the property that f ’ g p + g is de¬ned at Q.

Here g p denotes taking the pth power of each function value, so that Tr(g p ’ g) =

0. Note that for every function f ∈ Fq (C) and point Q ∈ C(Fq ) there exists a

function g ∈ Fq (C) such that either vQ (f ’ g p + g) ≥ 0 or vQ (f ’ g p + g) < 0 and

p |vQ (f ’ g p + g). De¬ne mQ = ’1 in the former case and mQ = ’vQ (f ’ g p + g)

in the latter. Of course mQ depends on f as well. When this is to be made explicit

mQ (f ) will be written instead of mQ . For more details see [Sti93, page 114].

Also observe that the quantity TrFq |Fp ((f ’ g p + g)(Q)) does not depend on g as

long as the function f ’ g p + g is de¬ned at Q. Thus, even if f itself is not de¬ned

in Q, the notation TrFq |Fp (f (Q)) will be used for Q ∈ C AS (f, Fq ).

Now de¬ne the sequence to be studied is given by:

De¬nition 5.4.2 Let E be an elliptic curve de¬ned over Fqe . Suppose that P is a

generator of the group [k(E, Fqe )]E(Fqe ) and denote its order by N . Let f ∈ Fqe (E).

The sequence S AS (f, P ) = {s(i)}0¤i<N is de¬ned by

s(i) = TrFqe |Fq (f ([i]P )).

Here the convention that TrFqe |Fq (f (Q)) = 0 if Q ∈ E AS (f, Fqe ) is used. Of course

this sequence depends on the elliptic curve as well, but this is not made explicit in

the notation.

Note that in the above notation N = l(E, Fqe ) and that if E(Fqe ) is cyclic, the

situation has already been studied in the literature [GBS00; VW00].