If ( P \ {O, [’d]P }) ‚ E K (h, Fq ) is demanded as well, the bound

√

1

CS K (f,P ) (d, ±, β) ¤ (2 + (3∆ + 3wdeg(f ) + 2) q)

N

is found.

Proof: Again B´zout™s theorem is to be used to estimate the number of zeros

e

of the function h. Using the addition formula (see for example [Sil86, Section

3.2]), (x, y) • (a, b) can be written as (g1 (x, y)/(x ’ a)2 , g2 (x, y)/(x ’ a)3 ) with

g1 (respectively g2 ) a polynomial in x and y of total degree less than or equal

5.6 Using linear recurrence relations on elliptic curves 63

to 2 (respectively 3). This means that ±f ((x, y) • (a, b)) can be written as

k(x, y)/(x ’ a)wdeg(f ) with k a polynomial of total degree less than or equal to

wdeg(f ). Hence, after multiplying the rational function h with (x ’ a)wdeg(f ) , a

polynomial of total degree less than or equal to ∆ + wdeg(f ) is obtained. This gives

an upper bound for the total number of zeros of the function h while its poles are

O and ’[d]P . The rest of the proof is analogous to the proof of Corollary 5.5.8.

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

acteristic p. Let P be a generator of the group [k(E)]E(Fq ) and write N = # P .

Let f1 and f2 be two functions and choose ±, β ∈ F— as well as a natural number

q

K K

0 ¤ d < N . Write S1 = S (f1 , P ) and S2 = S (f2 , P ). De¬ne h ∈ Fq (E) by

h(X) = ±f1 (X • [d]P ) ’ βf2 (X)

and suppose that the polynomial T m ’ h —¦ [k(E)] is absolutely irreducible. Then the

crosscorrelation is bounded by

«

rQ (h) ’ 1 √

1

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

|CS1 ,S2 (d, ±, β)| ¤ (1 ’ )q.

m’1

N

Q

Corollary 5.5.12 Let the notation be the same as in the above theorem. Sup-

pose that E is given by a Weierstrass equation. Further assume that f1 and f2

are non-trivial polynomials in the coordinate functions of total degree ∆1 and ∆2

with ∆1 ≥ ∆2 and satisfying degx (fi ) ¤ 2 with i = 1, 2. Further suppose that

gcd(wdeg(f1 ), m) = 1 if d = 0 and gcd(wdeg(±f1 ’ βf2 ), m) = 1 if d = 0. Then

√

1

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

CS1 ,S2 (d, ±, β) ¤

N

If ( P \ {O, [’d]P }) ‚ E K (h, Fq ) holds additionally, the following bound holds:

√

1

CS1 ,S2 (d, ±, β) ¤ (2 + (3∆2 + 3wdeg(f1 ) + 2) q) .

N

5.6 Using linear recurrence relations on elliptic curves

In this section the balance and the period of a family of sequences obtained by

using linear recurrence relations on the points of E will be investigated.

Suppose that G is a cyclic subgroup of E of order N generated by a point P ∈ E.

In this section, N will be assumed to be a prime number.

Let r(X) = X n + rn’1 X n’1 · · · + r0 be a monic polynomial of degree n > 1

over Z/N Z with gcd(r0 , N ) = 1 and let „¦(r, G) be the vector space over Z/N Z of

bi-in¬nite sequences of points in G that satisfy the linear recurrence relation with

characteristic polynomial r(X). This vector space has dimension n.

64 Pseudorandom sequences from elliptic curves

Suppose from now on that the characteristic polynomial r(X) of the recursion

is irreducible over Z/N Z. It is known from the theory of linear recurrencies (see for

example [Shp99, Chapter 7]) that if r(X) is irreducible, every sequence, apart from

the zero sequence, has the same period k(N, r). As a matter of fact k(N, r) is the

smallest positive integer k such that for every root ± of r(X) the relation ±k = 1

holds.

De¬ne Ψ(r, G) to be the set of sequences „¦(r, G) modulo cyclic shifts.

Lemma 5.6.1 Every point Q ∈ G occurs the same number of times in sequences

in Ψ(r, G), i.e. the number of pairs

# {(i, ψ) | 0 ¤ i < k(N, r); ψ(i) = Q; ψ ∈ Ψ(r, G)}

is independent of the choice of Q.

Proof: Since by de¬nition of the recursion polynomial r the greatest common

divisor of r0 and N is one and this polynomial has degree n, each sequence in

Ψ(r, G) is uniquely determined by the choice of n consecutive points. Conversely,

each n-tuple of points occurs exactly once in Ψ(r, G) (note that this is modulo cyclic

shifts). Since each point Q occurs equally often in the set of all n-tuples of points,

this is the case in Ψ(r, G) as well.

Let f ∈ Fqe be a function on E. Now look at the sequence S AS (f, P ) which was

de¬ned earlier by

S AS (f, P ) = TrFqe |Fq (f ([i]P )) .

0¤i<N

Furthermore, de¬ne the set of sequences Ψf (r, G) by applying the function f to each

point in each sequence in Ψ(r, G), and then taking the trace to the ground ¬eld Fq

of the result:

Ψf (r, G) = TrFqe |Fq (f (ψ)) |ψ ∈ Ψ(r, G) .

Note that each sequence of points in Ψ(r, G) corresponds with a sequence in Ψf (r, G).

Here, the same convention as before is used, namely that TrFqe |Fq (f (Q)) = 0 if

Q ∈ E AS (f, Fqe ).

Theorem 5.6.2 Choose a point P ∈ E. Let G be the subgroup of E generated

by P and suppose that its order is a prime N . Furthermore, let r be a monic

recursion polynomial of degree n whose zeroth coe¬cient is coprime to N . Then the

average balance of a sequence in Ψf (r, G) is the same as the balance of the sequence

S AS (f, P ).

Proof: Start by de¬ning the sequence T by merging all sequences of Ψf (r, G).

Since the order of points is not important in the de¬nition of balance and because

according to Lemma 5.6.1 each point occurs an equal number of times, we can

reorder the points of T such that we get a number of copies of the sequence

S AS (f, P ). Of course, this is the same sequence as S AS (f, P ) itself. Thus the

average balance of sequences in Ψf (r, G) is equal to the balance of the sequence

S AS (f, P ).

5.7 Conclusion 65

It is well known from the theory of linear recurrencies that the period of a

sequence can be larger than the group order. So sequences de¬ned in the above way

can have a larger period than the sequences described in the previous sections. But

this only applies to the sequences of points on E. The next theorem links this period

to the period of the generated pseudorandom sequence. The polynomial r(X) is still

supposed to be irreducible.

Theorem 5.6.3 Let r and G be de¬ned as in the above theorem. Suppose that the

order of G is a prime N and that the degree of the recursion polynomial is n. Denote

by Tf (a) the number of points Q in G for which TrFqe |Fq (f (Q)) = a. Suppose that

all sequences in Ψf (r, G) have period dividing k(N, r)/d. Then d is a divisor of

gcd(N ’ k(N, r), Tf (a), N n ’ 1) for all a ∈ Fq \{TrFqe |Fq (f (O))}.

Proof: All non-zero sequences in Ψf (r, G) have as period a divisor of k(N, r)/d.

Hence the number of times a occurs in the corresponding sequences is divisible by

d. Write b = TrFqe |Fq (f (O)). Then d divides N n Tf (a) with a ∈ Fq \ {b}, and d

divides N n Tf (b) ’ k(N, r). Since k(N, r) divides N n ’ 1, d divides gcd(N n Tf (b) ’

k(N, r), Tf (a), N n ’ 1) for all a ∈ Fq \ {b}. Using a∈Fq Tf (a) = N , for all a ∈

Fq \{TrFqe |Fq (f (O))} it is found (after eliminating Tf (b)) that d divides

gcd(N n+1 ’ k(N, r), Tf (a), N n ’ 1).

The result follows directly from this.

Example 5.6.4 Let E be the elliptic curve de¬ned over F2 given by the equation

Y 2 + Y = X 3 + X + 1.

Let G be a prime-order subgroup of E(Fq ) with q an odd power of 2. Using the

addition formulas on E, one can derive that for this curve Tx (0) ’ 1 = Tx (1) = (N ’

1)/2. Hence, according to the above theorem, d divides gcd((N ’ 1)/2, k(N, r) ’ 1).

Take for example r(X) = X 2 ’ X ’ 1, the Fibonacci-recursion. The polynomial

r(X) is irreducible if and only if N ≡ 2, 3 (mod 5). Assuming this, k(N, r) divides

2N + 2, since for any root ρ of r(X) the relation ρ2N +2 = (ρ · ρN )2 = (’1)2 = 1

holds. Here the fact was used that r(X) is absolutely irreducible and hence that its