Q

where the sum is over points Q such that Q ∈ P and Q ∈ E AS (h, Fqe ).

Proof: Note that CS AS (f,P ) (d, ±, β) = BS AS (h,P ) (1). Using similar techniques as

in the proof of Lemma 5.4.5, the result is obtained.

Using an upper bound for exponential sums, an upper bound for the autocor-

relation can be derived, if some technical conditions are met. More explicitly, the

following theorem is proven in the case that f is a polynomial in the coordinate

functions.

Theorem 5.4.8 Let E be an elliptic curve de¬ned over the ¬eld Fqe given by a

Weierstrass equation. Let f be a polynomial in the two coordinate functions x and

y, such that degy (f ) ¤ 1. Choose ±, β ∈ F— . Further choose a generator P of the

q

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

that the characteristic of Fq does not divide wdeg(f ). Then the autocorrelation can

be bounded as follows:

58 Pseudorandom sequences from elliptic curves

√

1

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

|CS AS (f,P ) (d, ±, β)| ¤

N

Analogously to the autocorrelation, properties about the crosscorrelations of

sequences can be derived. Some results are stated in the following theorem.

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

acteristic p, given by a Weierstrass equation. Let P be a generator of the group

[k(E)]E(Fqe ) and write N = # P . Let f1 and f2 be two polynomials in the coor-

dinate functions x and y such that degy (fi ) ¤ 1 for i = 1, 2, and such that for all

(±, β) ∈ Fqe \ {(0, 0)} the relation p |wdeg(±f1 ’ βf2 ) holds. Write S1 = S AS (f1 , P )

2

and S2 = S AS (f2 , P ). For all ±, β ∈ F— and 0 ¤ d < N the crosscorrelation can be

q

bounded as

√

1

2 + (2 + wdeg(f1 ) + wdeg(f2 )) q e ,

|CS1 ,S2 (d, ±, β)| ¤

N

unless d = 0 and ±f1 = βf2 .

Proof: This is a straightforward generalization of the proof of Theorem 5.4.8.

Now an example of a family of sequences having good crosscorrelations will be

given. In this example it is assumed that the characteristic is 2, since this is the

most interesting case for applications.

Example 5.4.10 Let E be an elliptic curve de¬ned over the ¬nite ¬eld F2e . Denote

by P a generator of the group [k(E)]E(Fqe ) and write N = # P . Let a be de¬ned

m+1

and let Sa be the binary sequence S AS (fa , P ) with

by a = (a0 , · · · , am ) ∈ F2e

de¬ning function fa = a0 y + · · · + am xm y.

n+1

For any number 0 ¤ d < N and a, b ∈ Fqe \ {0} the crosscorrelation of the two

sequences can be bounded as

√

1

2 + (2 + wdeg(fa ) + wdeg(fb )) 2e

|CSa ,Sb (d)| ¤ √

N

1

2 + (8 + 4m) 2e ,

¤ N

unless d = 0 and a = b.

5.5 Using multiplicative characters

Now multiplicative characters and Kummer extensions will be used to obtain

similar results as in the previous section, instead of additive characters and Artin-

Schreier extensions. Codes have been obtained using this approach in [Per91]. Se-

quences have been constructed in this way using the projective line in [Bar97]. Here

sequences will be constructed using elliptic curves.

5.5 Using multiplicative characters 59

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

a divisor of q ’ 1 and let f ∈ Fq (C). De¬ne C K (f, Fq ) to be the set of Fq -rational

points on C such that there exists a g ∈ Fq (C) such that vP (f · g m ) = 0.

Note that if φ : F— ’ Z/mZ is a homomorphism of groups, the quantity φ((f ·

q

g )(Q)) does not depend on g, as long as vQ (f · g m ) = 0. Hence, φ(f (Q)) will be

m

written instead of Q ∈ C K (f, Fq ), even if vQ (f ) = 0. In particular the quantity

f (Q)(q’1)/m is well-de¬ned for Q ∈ C K (f, Fq ). If Q ∈ C K (f, Fq ), a g ∈ Fq (C) can

always be found such that (f · g m )(Q) = 0. Hence f (Q)(q’1)/m is de¬ned to be

zero for Q ∈ C K (f, Fq ), even if f has a pole in Q. In the same way φ(f (Q)) = 0 is

de¬ned for Q ∈ C K (f, Fq ).

De¬nition 5.5.2 Let E be an elliptic curve de¬ned over Fq . Fix a natural number

1 < m < q ’ 1 dividing q ’ 1. Denote by χm : F— ’ Z/mZ some ¬xed, surjective

q

homomorphism of groups. Let P ∈ E(Fq ) and f ∈ Fq (E). De¬ne S K (f, P ) = {s(i)}

by

s(i) = χm (f ([i]P )).

The homomorphism χm is needed to de¬ne the balance and correlations of the

sequence S K (f, P ) (see Section 5.3). Note that χm (f (Q)) = 0 if Q ∈ E K (f, Fq ).

Example 5.5.3 Let Fp be a prime ¬eld with p odd. Let ± be a generator of the

multiplicative group F— . Let f [X] be a polynomial in Fp [X] of degree m. By evaluat-

p

ing this polynomial in all elements ±, ±2 , . . . of F— a codeword from a Reed-Solomon

p

code (RS-code) is obtained. A binary sequence is obtained from this codeword by

applying the map χ2 : Fp ’ Z/2Z coordinatewise, de¬ned by

±

0 if a = 0 or a = 1,

p

χ2 (a) =

1 if a = ’1.

p

a

Here, denotes the Legendre symbol, which indicates whether a is a quadratic

p

residue modulo p. If for example p = 13, f [X] = X 2 + X and ± = 2 are chosen the

codeword

(2, 6, 7, 7, 12, 3, 0, 2, 12, 4, 6, 4)

and corresponding binary sequence

(1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0)

are found.

As said before, it is possible to obtain codes using this construction. This was

done in [Per91]. There, non-linear codes were found and investigated. It is possible

to ¬nd interesting linear codes as is shown in the following example. After the

example, the study of sequences is resumed.

60 Pseudorandom sequences from elliptic curves

Example 5.5.4 Choose C to be the projective line de¬ned over some ¬nite ¬eld Fq

of odd characteristic. For M ‚ Fq (x)/(Fq (x))2 the group generated by the residue

classes of x ’ β is chosen, with β in some non-empty subset S of Fq . Then every

element of M has a representative of the form β∈S (x ’ β) β with β ∈ {0, 1}. As

a vector space over F2 , the group M has dimension #S. De¬ne χ2 as in Example

5.5.3. Evaluating χ2 —¦f in the set Fq \S for all functions f ∈ M, yields a binary linear

code C of length #(Fq \S). Its dimension is less than or equal to min(#S, #(Fq \S)).

Equality need not hold in this equation. Suppose for example that q is a square.

√

The evaluation of the polynomial f (X) = X q + X in an element a of Fq is either