zero or a square. To see this note that for a ∈ Fq the relation f (a) q = f (a)

holds, and hence either f (a) = 0 or f (a)(q’1)/2 = 1. Thus, if S is chosen to be

√ √

S = {a ∈ Fq | a q + a = 0}, the polynomial X q + x will correspond to the all-zero

codeword. This means that in this case the dimension of the code cannot equal the

cardinality of S. √

Note that the curve given by the equation Y 2 = X q + X has the maximum

number of Fq -rational points for its genus. As a matter of fact the number of Fq -

√ √

rational points can be seen to be 2q ’ q + 1, while its genus equals ( q ’ 1)/2.

The fact that it is maximal also follows from the fact that it can be covered by

√ √

the Hermitian curve which has equation Y q+1 = X q + X. Using the Hasse-Weil

bound and investigating the curve Y 2 = f (X), one can show that for sets S with

√

cardinality strictly smaller than q, only the zero-polynomial can give the all-zero

codeword. This means that in this case the dimension of the resulting codes equals

the cardinality of the set S.

Re¬ning this argument, it follows that the following statement holds for the

minimum distance d of these codes:

√

q ’ (#S ’ 1)( q ’ 1)

d≥ ’ #S,

2

√

which is a non-trivial lower bound if #S < q.

In a similar way as in the previous section statements about the balance, auto-

correlation and crosscorrelation of the sequences S K (f, P ) will be given.

De¬nition 5.5.5 Let C be an algebraic curve de¬ned over Fq . Let 1 < m < q ’ 1 be

a divisor of q ’ 1 and denote by χm : F— ’ Z/mZ some surjective homomorphism

q

of groups. Let f ∈ Fq (C). De¬ne the following exponential sum:

ES K (C, f ) = ζmm (f (P )) ,

χ

P ∈C K (f,Fq )

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

For this exponential sum a bound exists similar to that of the exponential sum

de¬ned in De¬nition 5.4.3. See for example [Per91], where similar upper bounds are

derived. The proof of the following proposition is analogous to that of Proposition

5.5 Using multiplicative characters 61

5.4.4. Instead of Artin-Schreier extensions, Kummer extensions are used (see for

example [Sti93, Section[3.7]).

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

f ∈ Fq (C) and suppose that f = z l for all z ∈ F(C) and all divisors l > 1 of m.

Write rP = gcd(m, vP (f )) > 0. Then the following holds:

«

rP ’ 1 √

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

m’1

P ∈E(Fq )

The rP occurring in the above proposition are standard in the theory of Kummer

extensions. When the role of f is to be stressed, rP (f ) will be written instead.

Theorem 5.5.7 Let E be an elliptic curve de¬ned over the ¬nite ¬eld Fq of charac-

teristic p. Let f ∈ Fq (E) be a function and write k = k(E, Fq ). Let P be a generator

of the group [k]E(Fq ). Suppose that the polynomial T m ’ f —¦ [k] is absolutely irre-

ducible. Then

«

rQ (f ) ’ 1 √

1

N ’ #(E K (f, Fq ) © P ) +

BS K (f,P ) ¤ (1 ’ )q,

m’1

N

Q

with N = # P .

Proof: Note that vQ (f —¦[k]) = v[k]Q (f ) and hence rQ (f —¦[k]) = r[k]Q (f ). Moreover,

note that rQ = m for Q ∈ E(Fq ), if and only if Q ∈ E K (f, Fq ). Hence it follows that

E K (f —¦ [k], Fq ) = [k]’1 E K (f, Fq ) © P . The rest of the proof is similar to that of

Lemma 5.4.5.

In the following corollary the weighted degree of a polynomial in two variables

de¬ned by wdeg(x) = 2 and wdeg(y) = 3 is used again.

Corollary 5.5.8 Let the notation be as in the above theorem and suppose that E is

given by a Weierstrass equation. Suppose that f is a non-trivial polynomial of total

degree ∆ in the coordinate functions x and y satisfying degx (f ) ¤ 2. Suppose that

gcd(wdeg(f ), m) = 1. Then the following bound holds:

√

1

N ’ #(E K (f, Fq ) © P ) + (3∆ + 1) q .

BS K (f,P ) ¤

N

If ( P \ {O}) ‚ E K (f, Fq ) is demanded as well, the bound

√

1

BS K (f,P ) ¤ (1 + (3∆ + 1) q)

N

holds.

62 Pseudorandom sequences from elliptic curves

Proof: This follows from the above theorem by remarking that by B´zout™s e

theorem (see for example [Wae40, Section 83]) f has at most 3∆ zeros on E. Further

note that the point O is the only pole f has on E. These zeros and poles are the only

points Q for which it can happen that rQ < m. Using that rQ ≥ 1 for these points

Q, the result follows. Note that rO (f —¦ [k(E)]) = rO (f ) = gcd(wdeg(f ), m) = 1.

Hence the polynomial T m ’ f —¦ [k(E)] is absolutely irreducible by the theory of

Kummer extensions.

Note that it can be useful to rewrite f , using the equation of E, in such a form

that the total degree is minimal. This explains why the assumption degx (f ) ¤ 2 is

made instead of degy (f ) ¤ 1, as was done previously.

Now some statements about the autocorrelation and crosscorrelations of these

sequences will be given. Most of the proofs will be omitted since they are analogous

to the proofs in the Artin-Schreier case.

Theorem 5.5.9 Let E be an elliptic curve de¬ned over the ¬eld Fq of characteristic

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

q

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

De¬ne h ∈ Fq (E) by

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

Suppose that the polynomial T m ’ h —¦ [k] is absolutely irreducible. Then

«

rQ (h) ’ 1 √

1

N ’ #(E K (h, Fq ) © P ) +

|CS K (f,P ) (d, ±, β)| ¤ (1 ’ )q.

m’1

N

Q

Corollary 5.5.10 Let the notation be the same as in the above theorem. Suppose

that E is given by a Weierstrass equation. Further assume that f is a non-trivial

polynomial in the coordinate functions of total degree ∆ satisfying degx (f ) ¤ 2 and

gcd(wdeg(f ), m) = 1. Then

√

1

N ’ #(E K (h, Fq ) © P ) + (3∆ + 3wdeg(f ) + 2) q .

CS K (f,P ) (d, ±, β) ¤