unnecessary. In this case any change of ordering gives rise to an equivalent code.

Indeed there is in that case no need of restricting oneself to elliptic curves. The

resulting codes are called trace-codes. They have been studied in for example [Sti93,

Chapter 8] and [Vos93].

Before some estimates for the parameters of the pseudorandom sequences de-

¬ned above are given, some more theory is needed. The key to the results is the

proposition about the following exponential sum:

5.4 Using additive characters 55

De¬nition 5.4.3 Let C be an algebraic curve de¬ned over Fq . Let f ∈ Fq (C). Now

look at the following exponential sum:

TrFq |Fp (f (P ))

ES AS (C, f ) = ζp ,

P ∈C AS (f,F q)

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

A known upper bound for this exponential sum is given in the next proposition.

Proposition 5.4.4 Let C be an algebraic curve of genus g de¬ned over Fq . Let

f ∈ Fq (C) and suppose that f = z p ’ z for all z ∈ F(C). Then the following holds:

«

√

ES AS (C, f ) ¤ 2g ’ 2 + (mP + 1) q.

P ∈C(Fq )

This proposition was proven in [Bom66; KS00; VW00]. The gist of the proof is

given here for the convenience of the reader.

Proof: The proposition can be rephrased by considering the curve D, de¬ned over

Fq whose function ¬eld is given by Fq (C)(z) with z p ’ z = f . Denote its genus by h.

The L-function of D is the product of the L-function of C with the following p ’ 1

expressions (1 ¤ i ¤ p ’ 1):

«

Te iTrF e |Fp (P )

ζp q

exp .

e AS

e≥1 P ∈C (f,Fqe )

As a matter of fact the above expressions turn out to be polynomials. By Hasse-

√

Weil™s theorem these polynomials have roots of length 1/ q and hence for all e ≥ 1

the following relation holds.

2(h ’ g) √ e

TrFqe |Fp (P )

¤

ζp q.

p’1

P ∈C AS (f,Fqe )

Using the theory for Artin-Schreier extensions an explicit expression for the genus h

can be derived (see for example [Sti93, Section 3.7]). This leads to the upper bound

given in the proposition.

By applying the above result an estimate for the parameters of the sequences

AS

S (f, P ) can now be given.

Theorem 5.4.5 Let E be an elliptic curve de¬ned over the ¬nite ¬eld Fqe of char-

acteristic p. Set k = k(E, Fqe ). Furthermore, let f ∈ Fqe (E) be a function and P be

a generator of the group [k]E(Fqe ).

Suppose that for all z ∈ F(E) the relation z p ’ z = f —¦ [k] holds and that

56 Pseudorandom sequences from elliptic curves

E AS (f —¦ [k], Fqe ) = [k]’1 E AS (f, Fqe ) © P .

Then BS AS (f,P ) is bounded from above by

«

√

1 1

N ’ #(E AS (f, Fqe ) © P ) + (mQ (f —¦ [k]) + 1) q e ,

k(E)2

N

Q

with N = # P .

Proof: Denote by S the sequence {TrFqe |Fq (f (Q))} with Q ∈ E AS (f, Fqe ) © P .

Further denote by T the sequence {TrFqe |Fq (f —¦ [k](Q))} with Q ∈ E AS (f —¦ [k], Fqe ).

The relation E AS (f —¦ [k], Fqe ) = [k]’1 E AS (f, Fqe ) © P holds and hence for each

point R in E AS (f, Fqe )© P , there exist exactly k 2 points Q in the set E AS (f —¦[k], Fqe )

such that [k]Q = R. Thus for any ± ∈ F— q

#E AS (f —¦ [k], Fqe )BT (±) = k 2 #(E AS (f, Fqe ) © P )BS (±).

So

BT (±) = BS (±).

Since

N · |BS AS (f,P ) (±)| ¤ N ’ #(E AS (f, Fqe ) © P ) + #(E AS (f, Fqe ) © P )|BS (±)|,

an upper bound for BT (±) results in an upper bound for BS AS (f,P ) . However, since

#E AS (f —¦ [k], Fqe )BT (±) = ES AS (E, f —¦ [k]) , such an upper bound is available from

Proposition 5.4.4. This concludes the proof.

Note that the technical condition

E AS (f —¦ [k], Fqe ) = [k]’1 E AS (f, Fqe ) © P

is ful¬lled if k = 1. Also note that the righthandside set is always contained in the

lefthandside set.

Now a special case of the above lemma is considered. Denote by wdeg(f (x, y))

the weighted degree of a polynomial in two variables de¬ned by wdeg(x) = 2 and

wdeg(y) = 3. Thus the weighted degree of a polynomial is equal to the highest

weighted degree of its monomials. Note that the choice of degrees for the monomials

x and y is natural for elliptic curves, since one works modulo the polynomial f (x, y),

and thus the weighted degree of y 2 should be equal to the weighted degree of x3 for

a consistent de¬nition.

Corollary 5.4.6 Let E be an elliptic curve de¬ned over the ¬nite ¬eld Fqe of char-

acteristic p given by a Weierstrass equation. Let f be a polynomial in the coordinate

5.4 Using additive characters 57

functions x and y such that degy (f ) ¤ 1. Further let P be a generator of the group

[k(E)]E(Fqe ) and de¬ne N = # P . Suppose that p does not divide wdeg(f ). Then

√

1

1 + (1 + wdeg(f )) q e .

BS AS (f,P ) ¤

N

Note that the above corollary also follows from [KS00, Theorem 1] or the work

of Bombieri [Bom66]. The condition degy (f ) ¤ 1 is not a real restriction, because

the Weierstrass equation can be used to reduce this degree if degy (f ) ≥ 2. Further

note that if this condition is met, the relation vO (f ) = ’wdeg(f ) holds where O is

the point at in¬nity [0 : 1 : 0]. For the proof of the above theorem one uses that

E AS (f, Fqe ) = E(Fqe ) \ {O} and that E AS (f —¦ [k(E)], Fqe ) = E(Fqe ) \ E[k(E)].

In the same way the autocorrelation of the sequences S AS (f, P ) can be investi-

gated. Before moving to the main theorem on this, a lemma is stated.

Lemma 5.4.7 Let E be an elliptic curve de¬ned over the ¬eld Fqe of characteristic

p. Let f ∈ Fqe (E) and choose ±, β ∈ F— . Write k = k(E, Fqe ) and choose a generator

q

P of the group [k]E(Fqe ) and a number d satisfying 1 ¤ d < N with N = # P .

De¬ne h ∈ Fqe (E) by

h(X) = ±f (X • [d]P ) ’ βf (X).

Denote by S the sequence {TrFqe |Fp (h —¦ [k](Q))} with Q ∈ E AS (h —¦ [k], Fqe ). Finally

suppose that E AS (h —¦ [k], Fqe ) = [k]’1 E AS (h, Fqe ) © P . Then

N · CS AS (f,P ) (d, ±, β) = c + #(E AS (h, Fqe ) © P )BS .

Here

TrFqe |Fp (h(Q))