Course 428

Elliptic Curves III

Dr Timothy Murphy

EELT1  Thursday, 2 May 2002  16:15–17:15

Attempt 3 questions. (If you attempt more, only the best 3 will be counted.) All questions carry the same number of marks.

1. State (without proof) Hasse’s Theorem on the number of points on an elliptic curve over a finite field. Show that the curve

ℰ (𝔽_{8}) : y^{2} + y = x^{3}

is elliptic, and find the number of points on it. Answer:

(a) Hasse’s Theorem states that the number N of points on an elliptic curve ℰ (𝔽_{q}) over the finite filed 𝔽_{q} satisfies

|N − (q + 1)| ≤ 2\sqrt{q}.

(b) In homogeneous coordinates the equation takes the form

F (X, Y, Z) = Y^{2}Z + Y Z^{2} + X^{3} = 0

(using the fact that the field is of characteristic 2). Thus

\frac{∂F}{∂X} = X^{2},
\frac{∂F}{∂Y} = Z^{2},
\frac{∂F}{∂Z} = Y^{2}.

Thus at a singular point X = Y = Z = 0, which is impossible.

(c) The polynomial

p(x) = x^{3} + x + 1

is irreducible over 𝔽_{2}, since p(0) ≠ 0, p(1) ≠ 0. Thus

F_{8} = F_{2}[x]/(p(x)).

Let α = x mod p(x). Then the elements of F_{8} are

c_{0} + c_{1}α + c_{2}α^{2},

where c_{0}, c_{1}, c_{2} ∈ {0, 1}; and

α^{3} = α + 1.

Since |F_{8}^{×}| = 7 there are no elements of order 3 in 𝔽_{8}^{×}. Thus the homomorphism

x ↦ x^{3} : 𝔽_{8}^{×} → 𝔽_{8}^{×}

has trivial kernel, and so is an isomorphism. In other words, each element of 𝔽_{8}^{×} has a unique cube-root; and this is evidently true of the element 0 too. It follows that for each choice of y we can find just one x with x^{3} = y^{2} + y. Thus there are 8 points on the affine curve; and so, on adding the point O = [0, 1, 0],

|ℰ (𝔽_{8})| = 9.

2. Show that there are no rational numbers x, y such that

y^{2} = x^{4} + 2.

Answer: To bring this hyper-elliptic equation to elliptic form we rewrite it as

(y − x^{2})(y + x^{2}) = 2.

Now set

s = y + x^{2}.

Then

y − x^{2} = \frac{2}{s}.

Thus

2x^{2} = s − \frac{2}{s}.

Multiplying across by s^{2},

2s^{2}x^{2} = s^{3} − 2s.

Setting sx = t,

2t^{2} = s^{3} − 2s.

Explicitly,

(s, t) = (y + x^{2}, xy + x^{3}),

while the inverse map is

(x, y) = (t/2, s − t^{2}/4).

Now set x = s/2, y = t/4. We obtain the elliptic curve

ℰ (ℚ) : y^{2} = x^{3} − 8x.

The associated elliptic curve is

ℰ_{1}(ℚ) : y^{2} = x^{3} + 32x.

Since ℰ has just one point of order 2, while b_{1} = 32 is not a perfect square, the rank r of ℰ is given by

2^{r+1} = \frac{| im χ| · | im χ_{1}|}{2},

where

χ : ℰ → ℚ^{×} → ℚ^{×2}, χ : ℰ_{1} → ℚ^{×} → ℚ^{×2}

are the auxiliary homomorphisms.

We have

im χ ⊂ {±1, ±2}, im χ_{1} ⊂ {±1, ±2}.

Since χ(0, 0) = −8 ∼ −2,

im χ = {1, −2} or {±1, ±2}.

Recall that d ∈ im χ if and only if the equation

du^{4} + d′t^{4} = v^{2},

where d′ = b/d, has an integral solution with gcd(u, t) = 1 = gcd(v, t). Taking d = −1 we have d = 8 and the equation is

−u^{4} + 8t^{4} = v^{2}.

If v is odd then so is u. But then u^{4} ≡ 1 mod 4 and v^{2} ≡ 1 mod 4, which is a contradiction.

Hence v is even, and so u is even. But then

2 | u ⟹ 16 | u^{4}
⟹ 8 | v^{2}
⟹ 4 | v
⟹ 16 | v^{2}
⟹ 2 | t,

contradicting the assumption that gcd(t, u) = 1.

It follows that

im χ = {1, −2}.

For im χ_{1} we note that d < 0 ⟹ d′ = 32/d < 0, in which case u = t = v = 0, which is absurd. On the other hand, χ_{1}(0, 0) = 2. Thus

im χ_{1} = {1, 2}.

We conclude that r = 0, ie the group on the curve is finite.

To find the points of finite order, we recall that if χ(x, y) = (x_{1}, y_{1}) then

x_{1} = \frac{x^{2} − 8}{x}.

But if P = (x, y) is of finite order then so is (x_{1}, y_{1}). Hence

x, x_{1} ∈ ℤ.

Thus x ∈ {±1, ±2, ±4, ±8}. But it is a trivial matter to verify that none of these make x^{3} − 8x a perfect square. Thus ℰ contains only the point (0, 0).

But no point (x, y) on the original curve gives rise to this point. (More precisely, the point (0, 0 on ℰ corresponds to a point on the line at infinity on the original curve.) We conclude that the original equation has no rational solution.

3. Show that a non-singular cubic Γ over the field k can be brought to Weierstrassian form if and only if there is a point P ∈ Γ defined over k.

Bring the curve

X^{3} + Y^{3} + Z^{3} = XY Z

to Weierstrassian form.

Show that the cubic

X^{3} + 2Y^{3} + 4Z^{3} = 0

is non-singular, but has no rational point.

Answer:

(a) Let P be a rational point on Γ. If P is a point of inflexion then we can bring P to the point [0, 1, 0] and the tangent at P to the line Z = 0 by a projective transformation. Since the line Z = 0 meets Γ where X^{3} = 0 it follows that the coefficients of Y^{3}, XY^{2}, X^{2}Y all vanish. Thus Γ takes the form

F (X, Y, Z) = AY^{2}Z+BXY Z+CY Z^{2}+DX^{3}+EX^{2}Z+F XZ^{2}+GZ^{3} = 0.

If D = 0 then Z is a factor, so the curve is degenerate and therefore singular. If A = 0 then

∂F/∂X = ∂F/∂Y = ∂F/∂Z = 0

at P = [0, 1, 0], so again the curve is singular. Thus the curve takes the inhomogeneous form

y^{2} + axy + by = cx^{3} + dx^{2} + ex + f,

with c ≠ 0. But now the transformation x′ = cx, y′ = xy makes the coefficients of y^{2} and x^{3} equal, bringing the curve to Weierstrassian form. Suppose now that P is not a flex. Let the tangent at P meet the curve again at Q, and let the tangent at Q meet the curve again at R. We may suppose that Q is not a flex, so that P, Q, R are non-collinear and can be brought by a projective transformation to the points [1, 0, 0], [0, 1, 0], [0, 0, 1]. Since the curve goes through these three points, the coefficients of X^{3}, Y^{3}, Z^{3} all vanish. Since the tangent at [1, 0, 0] is Z = 0, the coefficient of X^{2}Y vanishes; and since the tangent at [0, 1, 0] is X = 0, the coefficient of Y^{2}Z vanishes. Thus the curve takes the form

aXY^{2} + bXY Z + cY Z^{2} = dX^{2}Z + eXZ^{2},

or in inhomogeneous form,

axy^{2} + bxy + cy = dx^{2} + ex.

Multiplying by x, and setting xy = y′,

ay′^{2} + bxy′ + cy′ = dx^{3} + ex^{2}.

The transformation (x, y′) = (x, xy) is birational, with inverse (x, y) = (x, y′/x). As above, the curve is singular if a = 0 or d = 0; and the transformation y′′ = λy′, x′′ = λx with λ = a/d brings the curve to Weierstrassian form.

(b) If

F (X, Y, Z) = X^{3} + Y^{3} + Z^{3} + XY Z

then

\frac{∂F}{∂X} = 3X^{2} + Y Z,
\frac{∂F}{∂Y} = 3Y^{2} + XZ,
\frac{∂F}{∂Z} = 3Z^{2} + XY.

At a singular point,

3X^{2} = −Y Z, 3Y^{2} = −XZ, 3Z^{2} = −XY ⟹ 27X^{2}Y^{2}Z^{2} = −X^{2}Y^{2}Z^{2}
⟹ XY Z = 0
⟹ X = Y = Z = 0.

Thus the curve is non-singular. Let P = [1, −1, 0]. The tangent at P is

3X + 3Y − Z = 0.

This meets the curve again where

(X^{3} + Y^{3}) + 27(X + Y)^{3} + 3XY (X + Y) = 0,

ie

(X + Y) [(X^{2} − XY + Y^{2}) + 3XY + 27(X + Y)^{2}]

ie

28(X + Y)^{3}.

Thus the tangent meets the curve three times at P, ie P is a point of inflexion. Hence we can bring the curve to Weierstrassian form by a projective transformation taking the point [1, −1, 0] to [0, 1, 0] and the line 3X + 3Y − Z = 0 to Z = 0. A suitable transformation is

X′ = X + Y, Y′ = Y, Z′ = Z − 3(X + Y),

or inversely,

X = X′ − Y′, Y = Y′, Z = 3X′ + Z′.

The equation becomes

(X′ − Y′)^{3} + Y^{′3} + (3X′ + Z′)^{3} + (X′ − Y′)Y′(3X′ + Z′) = 0, ie

28X^{′3} + 27X^{′2}Z′ + 9X′Z^{′2} + Z^{′3} + X′Y′Z′ − Y^{′2}Z′ = 0,

or in affine coordinates

y^{′2} − x′y′ = 28x^{′3} + 27x^{′2} + 9x′ + 1.

The transformation

x′ = x/28, y′ = y/28

brings this to Weierstrassian form

y^{2} − xy = x^{3} + 27x^{2} + 9 · 28x + 28^{2}.

(c) Suppose X, Y, Z (not all 0) satisfy

X^{3} + 2Y^{3} + 4Z^{3} = 0

We may suppose without loss of generality that gcd(X.Y.Z) = 1. Evidently 2 | X, say X = 2X′. Then

8X′^{3} + 2Y^{3} + 4Z^{3} = 0,

ie

4X′^{3} + Y^{3} + 2Z^{3} = 0.

Now 2 | Y, say Y = 2Y′; and

4X′^{3} + 8Y′^{3} + 2Z^{3} = 0,

ie

2X′^{3} + 4Y′^{3} + Z^{3} = 0.

But now 2 | Z, contradicting our assumption that gcd(X, Y, Z) = 1.

4. Outline Pollard’s p − 1 method for factorizing large numbers, and Lenstra’s Elliptic Curve development of this.

What advantage does Lenstra’s method possess?

Answer:

Pollard’s p − 1 method Suppose n is a large composite number. (It is easy to establish that n is composite, by the Miller-Rabin algorithm.) Let p be a prime factor of n. Recall that a number m is said to be b-smooth, where b is a relatively small number, if every for every prime factor q of m the highest power of q dividing m is ≤ b:

q^{e} | m ⟹ q^{e} ≤ b.

This is the same as saying that

m | k,

where

k = k(b) = ∏_{p≤b} p^{e(p)},

where e(p) is the exponent of the highest power of p such that

p^{e(p)} ≤ b.

Now suppose that p − 1 is b-small. Then

p − 1 | k.

By Fermat’s Little Theorem, if a is coprime to p then

a^{p−1} ≡ 1 mod p.

Hence

a^{k} ≡ 1 mod p,

ie

p | a^{k} − 1,

and so

d = gcd(a^{k} − 1, n) > 1.

It is improbable that d = n; so d gives a proper factor of n. To summarise, we choose a small number a, compute a^{k} mod n (working throughout mod n) and then calculate d = gcd(a^{k}−1, n).

Lenstra’s elliptic curve method Suppose as before that n is a large composite integer, and that p is a prime factor of n. Let

ℰ (ℚ) : y^{2} = x^{3} + bx + c (b, c ∈ ℤ)

be an elliptic curve; and let ℰ (𝔽_{p}) be the reduction of ℰ mod p. We may suppose that the reduction is good, ie ℰ (𝔽_{p}) is an elliptic curve. For if it is not then

p | Δ = −(4b^{3} + 27c^{2})

and so

d = gcd(Δ, n) > 1

will almost certainly provide a proper factor of n. Let the order of the group ℰ (𝔽_{p}) be N. By Hasse’s Theorem, N is roughly equal to p; more precisely,

|N − (p + 1)| ≤ 2\sqrt{p}.

Now suppose N is b-small. Then

N | k

as in Pollard’s method. Let us choose a point

P = [X, Y, Z] (X, Y, Z ∈ ℤ)

on ℰ (ℚ); and set

rP = [X_{r}, Y_{r}, Z_{r}]

for r ∈ ℕ. Let P_{p} denote the reduction of P mod p. By Lagrange’s Theorem,

NP_{p} = 0,

and so

kP_{p} = 0,

ie

kP_{p} = [0, 1, 0].

Thus

Z_{k} ≡ 0 mod p.

Hence

d = gcd(Z_{k}, n) > 1;

and we may expect d to be a proper factor of n. Note that we can compute the coordinates of rP as polynomials (with integer coefficients) in X, Y, Z. In effect if

P_{1} = [X_{1}, Y_{1}, Z_{1}], P_{2} = [X_{2}, Y_{2}, Z_{2}]

and

P_{3} = P_{1} + P_{2} = [X_{3}, Y_{3}, Z_{3}]

then

X_{3}, Y_{3}, Z_{3} ∈ ℤ[X_{1}, Y_{1}, Z_{1}, X_{2}, Y_{2}, Z_{2}].

Note that we can work throughout modn. Thus the computation of kP mod n requires approximately log k additions and doublings of points modn. Note too that it is simplest to choose the point P = [X, Y, Z] and then find an elliptic curve y^{2} = x^{3} + bx + c containing this point.

Comparison We can choose many different elliptic curves y^{2} = x^{3} + bx + c. We may expect that as the curve varies the order N of the reduced curve will be randomly distributed over the range (p + 1 − 2\sqrt{p}, p + 1 + 2\sqrt{p}) allowed by Hasse’s Theorem. Thus there is a far greater chance of finding a curve with b-small order N than there is with Pollard’s method which relies on the single number p − 1 being b-small.