Course 374 (Cryptography)

Sample Paper 2

Dr Timothy Murphy

GMB ??  Friday, ?? 2007  ??:00–??:00

Attempt 4 questions from Part A, and 2 questions from Part B.

Part B

7. Show that the number of elements in a finite field is a prime power p^{e}; and show that there is exactly one field (up to isomorphism) with p^{e} elements.

Answer:

(a) Suppose k is a finite field of characteristic p. Then the elements 0, 1, 2, …, p − 1 form a subfield isomorphic to 𝔽_{p} = ℤ/(p). We can consider k as a vector space over this subfield 𝔽_{p}. If the vector space is of dimension d with basis e_{1}, …, e_{d} then k consists of the p^{d} elements

x = λ_{1}e_{1} + ⋯ + λ_{d}e_{d},

with λ_{i} ∈ {0, 1, …, p − 1}.

(b) We have to show

i. There exists a field containing p^{n} elements. ii. Two fields containing p^{n} elements are isomorphic;

i. Let

U_{n}(x) = x^{p^{n}} − x ∈ 𝔽_{p}[x].

We can construct a splitting field K for U_{n}(x), ie a field in which U_{n}(x) factorises completely into linear factors, by repeatedly adjoining roots of U_{n}(x):

𝔽_{p} = k_{0} ⊂ k_{1} ⊂ ⋯ ⊂ k_{r} = K,

where

k_{i+1} = k_{i}(θ_{i}).

More precisely, suppose U_{n}(x) factorises over k_{i} into irreducible factors, as

U_{n}(x) = f_{1}(x) ⋯ f_{s}(x).

If all the factors are linear, we are done. If not, say f_{1}(x) is not linear, then we adjoin a root of f_{1}(x), ie we set

k_{i+1} = k_{i}[x]/(f_{1}(x)).

This ‘splits off’ a new linear factor (x − θ_{i}), where θ_{i} is a root of f_{1}(x), and so of U_{n}(x). Since U_{n}(x) has at most p^{n} such factors, the process must end after at most p^{n} iterations. The polynomial U_{n}(x) splits completely in K, say

U_{n}(x) = (x − α_{1}) ⋯ (x − α_{p^{n}}).

The factors must be distinct, ie U_{n}(x) is separable, since

U′_{n}(x) = 1

and so

gcd(U_{n}(x), U′_{n}(x)) = 1.

We claim that the roots

k = {α_{1}, …, α_{p^{n}}}

form a subfield of k, containing p^{n} elements. For suppose α, β ∈ k. Then

α^{p^{n}} = α, β^{p^{n}} = α ⟹ (αβ)^{p^{n}} = αβ
⟹ αβ ∈ k,

while also

(α + β)^{p^{n}} = α^{p^{n}} + β^{p^{n}} = α + β ⟹ α + β ∈ k.

Thus we have constructed a field with p^{n} elements. ii. Suppose k, k′ are two field with p^{n} elements. We assume the

following result: Lemma 1. If k is a finite field then the multiplicative group

k^{×} = k \ {0}

is cyclic. Let π ∈ k be a generator of k^{×} (ie a primitive element of k). Suppose the minimal polynomial of π over 𝔽_{p} is m(x). We also assume the following result (an easy consequence of Lagrange’s Theorem): Lemma 2. If the field k contains p^{n} elements, say

k = {α_{1}, …, α_{p^{n}}}

then

U_{n}(x) = ∏_{α∈k}(x − α).

It follows in particular that

U_{n}(π) = 0.

Hence

m(x) | U_{n}(x).

Passing to k′, since

U_{n}(x) = ∏_{α′∈k′}(x − α′)

and

m(x) | U_{n}(x)

it follows that there is an element π′ ∈ k′ satisfying

m(π′) = 0.

Since m(x) is irreducible, it is the minimal polynomial of π′. Hence if f(x) ∈ 𝔽_{p}[x] then

f(π) = 0 ⟺ m(x) | f(x) ⟺ f(π′) = 0.

In particular, π′ is a primitive element of k′, since

π′^{d} = 1 ⟹ π′ is a root of x^{r} − 1
⟹ π is a root of x^{r} − 1
⟹ π^{d} = 1.

Now we define a map

θ : k → k′

by setting

θ(π^{r}) = π′^{r},

together with 0 ↦ 0. We note that θ is well-defined, since π, π′ have the same order. Suppose

α = π^{r}, β = π^{s}.

Then

θ(αβ) = θ(π^{r+s})
= π′^{r+s}
= θ(α)θ(β).

Also

α + β = π^{t} ⟹ f(π) = 0,

where

f(x) = x^{r} + x^{s} − x^{t}.

In this case

f(π′) = 0 ⟹ π′^{r} + π′^{s} = π′^{t}
⟹ θ(α) + θ(β) = θ(α + β).

It is trivial to show that these results also hold if one or more of α, β, α + β is 0. Hence

θ : k → k′

is a ring-homomorphism. Moreover, θ is injective since

θ(π^{r}) = 0 ⟹ π′^{r} = 0 ⟹ π = 0.

which is impossible. Hence θ is an isomorphism.

8. Show that a finite abelian group A is the direct sum of its p-primary parts A_{p} (consisting of the elements of order p^{e} for some e).

Determine whether the equation

y^{2} + xy = x^{3} + 1

defines an elliptic curve over each of the fields 𝔽_{2}, 𝔽_{3}, 𝔽_{4}, 𝔽_{5}, 𝔽_{7}, 𝔽_{8}, 𝔽_{9}; and in those cases where it does, determine the group on the curve.

Answer:

(a) Suppose

|A| = n = p_{1}^{e_{1}} ⋯ p_{r}^{e_{r}}

Let

q_{i} = ∏_{j≠i} p_{j}^{e_{j}} = \frac{n}{p_{i}^{e^{i}}} .

Then q_{1}, …, q_{r} are co-prime, and so (by the Chinese Remainder Theorem) we can find m_{1}, …, m_{r} such that

m_{1}q_{1} + ⋯ + m_{r}q_{r} = 1.

Thus if a ∈ A then

a = m_{1}q_{1}a + ⋯ + m_{r}q_{r}a.

But

m_{i}q_{i}a ∈ A_{p_{i}}

since

p_{i}^{e_{i}}(m_{i}q_{i}a) = m_{i}(p_{i}^{e_{i}}q_{i})a
= m_{i}(na)
= 0.

Thus

A = A_{p_{1}} + ⋯ + A_{p_{r}}.

It remains to show that the sum is direct. Suppose

a_{1} + ⋯ + a_{r} = 0,

where a_{i} ∈ A_{p_{i}}.

By Lagrange’s Theorem,

p_{j}^{e_{j}}a_{j} = 0.

It follows that

q_{i}a_{j} = 0

if i ≠ j. Hence

q_{i}a_{i} = 0

But since

gcd(p_{i}^{e_{i}}, q_{i}) = 1

we can find r, s such that

rp_{i}^{e_{i}} + sq_{i} = 1.

Then

a_{i} = rp_{i}^{e_{i}}a_{i} + sq_{i}a_{i}
= 0 + 0.

Thus

a_{1} = ⋯ = a_{r} = 0,

and so the sum is direct.

(b) k = 𝔽_{2} The equation takes the homogeneous form

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

We have

∂F/∂X = Y Z + X^{2},
∂F/∂Y = XZ,
∂F/∂Z = Y^{2} + XY + Z^{2}.

At a singular point,

XZ = 0 ⟹ X = 0 or Z = 0.

But

X = 0 ⟹ Y Z = 0, Y^{2} + Z^{2} = 0 ⟹ Y = Z = 0,

while

Z = 0 ⟹ X = 0 ⟹ Y = 0.

Thus there is no singular point, and we have an elliptic curve. Returning to the inhomogeneous equation,

x = 0 ⟹ y^{2} = 0 ⟹ y = 0,

while

x = 1 ⟹ y^{2} + y = 0,

which is true for y = 0, 1. Thus there are 3 affine points (0, 1), (1, 0), (1, 1) on the curve, which together with the point at infinity gives a group of order 4. We have to determine if the group is

ℤ/(4) or ℤ/(2) ⊕ ℤ/(2).

We can distinguish between these by the number of elements of order 2; the first group has 1, the second has 3. Suppose P = (x_{0}, y_{0}), Then −P is the point where the line OP through the point at infinity O = [0, 1, 0] meets the curve again. This is the line

x = x_{0}.

Thus P is of order 2, ie −P = P, if and only if this line meets the curve just once. Since there is only 1 point with x = 0, the line x = 0 meets the curve twice at A = (0, 0). Thus A is of order 2. There are two points on the line x = 1, so neither is of order 2. We conclude that the group is ℤ/(4).

k = 𝔽_{3} Completing the square on the left, the equation becomes

(y + x/2)^{2} = x^{3} + x^{2}/4 + 1,

ie

y′^{2} = x^{3} + x^{2} + 1,

on setting y′ = y+x/2 = y−x and noting that 1/4 = 1 mod 3. The polynomial p(x) = x^{3} + x^{2} + 1 is separable, since p′(x) = 2x and so gcd(p(x), p′(x)) = 1. Hence the curve is elliptic. The quadratic residues mod3 are 0, 1.

We draw up a table for x, x^{3} + x^{2} + 1 and possible y:

\begin{matrix}x & x^{3} + x^{2} + 1 & y′ \\ 0 & 1 & ±1 \\ 1 & 0 & 0 \\ −1 & 1 & ±1 \end{matrix}

Thus the curve has 6 points (including the point at infinity). There is only one abelian group of order 6, namely ℤ/(6), so we conclude that this is the group on the curve.

k = 𝔽_{4} The argument in the case k = 𝔽_{2} shows that the curve is non-singular, ie an elliptic curve E(𝔽_{4}). Also

E(𝔽_{2}) = ℤ/(4)

is a subgroup:

E(𝔽_{2}) ⊂ E(𝔽_{4}).

In particular, E(𝔽_{4}) is of order 4m for some m. Suppose P = (a, b) ∈ E(𝔽_{4}). The line

OP : x = a

meets the curve where

y(y + a) = a^{3} + 1.

Thus OP meets the curve again at

−P = (a, y + a).

Note that

−P = P ⟺ a = 0 ⟺ P = (0, 1).

It follows that there is just 1 point of order 2. If x ∈ 𝔽_{4}^{×} then

x^{3} = 1,

and so the equation reduces to

y(y + x) = 0.

Thus there are 2 solutions (x, 0), (x, x) for each x ∈ 𝔽_{4} \ 𝔽_{2}. It follows that there are 8 points on the curve. Since there is a subgroup ℤ/(4) the group is either

ℤ/(8) or ℤ/(4) ⊕ ℤ/(2).

Since there is only one point of order 2, we conclude that the group is ℤ/(8). k = 𝔽_{5} In this case 1/4 = −1 and the curve takes the form

y^{2} = p(x) ≡ x^{3} − x^{2} + 1.

Since

p′(x) = 3x^{2} − 2x = 3x(x + 1).

Since neither 0 nor 1 is a root of p(x), the polynomial is separable, and the curve is elliptic. The quadratic residues mod5 are {0, ±1}. We draw up a table as before:

\begin{matrix}x & x^{3} − x^{2} + 1 & y \\ 0 & 1 & ±1 \\ 1 & 1 & ±1 \\ 2 & 0 & 0 \\ −1 & −1 & ±2 \\ −2 & −1 & ±2 \end{matrix}

Thus there are 9 + 1 = 10 points on the curve. Hence the group is ℤ/(10).

k = 𝔽_{7} Since 1/4 = 2 in this case, the equation is

y^{2} = p(x) ≡ x^{3} + 2x^{2} + 1.

We have

p′(x) = 3x^{2} + 4x = 3x(x − 1).

Since neither 0 nor 1 is a root of p(x), the polynomial is separable, and the curve is elliptic. The quadratic residues mod7 are {0, 1, 2, −3}. We draw up a table as before:

\begin{matrix}x & x^{3} + 2x^{2} + 1 & y \\ 0 & 1 & ±1 \\ 1 & −3 & ±2 \\ 2 & 2 & ±3 \\ 3 & −3 & ±2 \\ −1 & 2 & ±3 \\ −2 & 1 & ±1 \\ −3 & −1 & − \end{matrix}

Thus there are 12 + 1 = 13 points on the curve. Hence the group is ℤ/(13). k = 𝔽_{8} The argument in the cases 𝔽_{2} and 𝔽_{4} remains valid here;

the curve is non-singular and so elliptic. As before, we can write the equation as

y(y + x) = x^{3} + 1.

Thus the points appear in pairs P = (x, y), −P = (x, y + x), except when x = 0, in which case there is just one point (0, 1) of order 2. Also, as in the case 𝔽_{4},

E(𝔽_{2}) = ℤ/(4) ⊂ E(𝔽_{8}),

and in particular there are 4n points for some n. [But note that 𝔽_{4} is not a subfield of 𝔽_{8}.] The Frobenius automorphism

Φ : (x, y) ↦ (x^{2}, y^{2})

has order 3; so either

Φ(P) = P ⟺ P ∈ E(𝔽_{2})

or else there is a triplet of points

{P, ΦP, Φ^{2}P }.

It follows that the number of points in E(𝔽_{8})\E(𝔽_{2}) is divisible by 3, as well as 4. Since there are at most 2 values of y for each of the 8 values of x, there are at most 16 points on the curve (there is just one point for x = 0 to balance the additional point at infinity). It follows that the curve contains either 4 or 16 points. Hasse’s Theorem tells us that the number N of points on the curve satisfies

|N − 9| ≤ 2\sqrt{8} < 6,

from which it follows that

4 ≤ N ≤ 14.

Hence N = 4, and so the group is ℤ/(4). k = 𝔽_{9} As in the case 𝔽_{3}, we can complete the square on the left

and the curve takes the form

y^{2} = p(x) ≡ x^{3} + x^{2} + 1.

We know that

E(𝔽_{3}) = ℤ/(6) ⊂ E(𝔽_{9}).

In particular the curve has 6m points for some m. Recall that the point (x, y) is of order 2 if y = 0 and p(x) = 0. We know that (1, 0) is one such point. In fact

p(x) = (x − 1)(x^{2} − x − 1).

The polynomial g(x) = x^{2} − x − 1 is irreducible over 𝔽_{3} (since none of {0, ±1} are roots). It follows that

𝔽_{9} = 𝔽_{3}[x]/(g(x)).

Hence

g(x) = (x − α)(x − β)

with α, β ∈ 𝔽_{9}. Thus there are 3 points of order 2 on the curve. Hence the 2-primary part of the group contains at least 4 points, and so the curve contains 12n points for some n. There are at most 2 points for each x ∈ 𝔽_{9}. [In fact only 1 for x = 1, α, β.] It follows that the curve has 12 points. Since there are 3 points of order 2, the 2-primary part is ℤ/(2) ⊕ ℤ/(2). Hence the group is

ℤ/(2) ⊕ ℤ/(2) ⊕ ℤ/(3) = ℤ/(6) ⊕ ℤ/(2).

9. Show that the map

Φ : x ↦ x^{p}

is an automorphism of the finite field 𝔽_{p^{e}}; and show that every automorphism of this field is of the form Φ^{r} for some r.

Find an irreducible polynomial f(x) of degree 5 over 𝔽_{2}. Hence or otherwise determine the group on the elliptic curve

y^{2} + y = x^{3} + x

over 𝔽_{2^{5}}.

Answer:

(a) We have

Φ(xy) = (xy)^{p}
= x^{p}y^{p}
= Φ(x)Φ(y)

while

Φ(x + y) = (x + y)^{p}
= x^{p} + y^{p}
= Φ(x) + Φ(y),

since

p | \binom{n}{r}

for r = 1, …, n − 1. Thus Φ is a ring-homomorphism. Moreover, Φ is injective since

Φ(x) = 0 ⟹ x^{p} = 0 ⟹ x = 0.

Hence Φ is bijective (since the field is finite), ie Φ is an automorphism.

(b) Suppose Θ is an automorphism of k = 𝔽_{p^{e}}. By definition Θ(1) = 1. Hence Θ leaves invariant the elements of the prime subfield 𝔽_{p}. We assume the following result:

Lemma 3. Suppose f(x) is an irreducible polynomial of degree e over 𝔽_{p}. Then f(x) factorizes completely over 𝔽_{p^{e}}; and if α is one root then the others are

Φ(α), Φ^{2}(α), Φ^{e−1}(α).

[This follows from the fact that the polynomial

∏_{0≤i<e}(x − Φ^{i}α)

is fixed under Φ, and so has coefficients in 𝔽_{p}.]

Let π be a primitive element of k. Then Θ is completely determined by Θ(π), since

Θ(π^{r}) = Θ(π)^{r}.

Suppose m(x) is the minimal polynomial of π over 𝔽_{p}. Then Θ leaves m(x) invariant, since it leaves 𝔽_{p} invariant. It follows that Θ permutes the roots of m(x). But by the Lemma, these roots are π, Φπ, …, Φ^{e−1}π. Hence

Θπ = Φ^{r}π

for some r. It follows that

Θ = Φ^{r}.

(c) If a polynomial of degree 5 is reducible then it must have a factor of degree 1 or 2. There is just one irreducible polynomial of degred 2 over 𝔽_{2}, namely m(x) = x^{2} + x + 1. Thus a polynomial f(x) ∈ 𝔽_{2}[x] of degree 5 is irreducible unless it is divisible by x, x + 1 or m(x). Also

x^{3} ≡ 1 mod m(x),

since

x^{3} − 1 = (x − 1)m(x).

Let

f(x) = x^{5} + x^{2} + 1.

Then

f(0) = f(1) = 1,

while

f(x) ≡ x^{2} + x^{2} + 1 = 1 mod m(x)

since x^{5} ≡ x^{2}. Hence f(x) is irreducible.

(d) Let us first verify that the curve is non-singular. The equation takes homogeneous form

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

We have

∂F/∂X = X^{2} + Z^{2},
∂F/∂Y = Z^{2},
∂F/∂Z = Y^{2}.

Thus at a singular point,

Y = Z = 0 ⟹ X = 0.

Hence there are no singular points, and the curve is elliptic. Three ideas help us determine the group on the curve:

i. Consider the points on the curve defined over 𝔽_{2}, forming the subgroup E(𝔽_{2}) ⊂ E(𝔽_{2^{5}}). It is readily verified that all 4 affine points

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

lie on the curve. Adding the point at infinity, it follows that

E(𝔽_{2}) = ℤ/(5).

In particular E(𝔽_{2^{5}}) contains 5m points, for some m. ii. The equation can be written

y(y + 1) = x^{3} + x.

It follows that if P = (a, b) is on the curve then so is −P = (a, b + 1). (This second point is −P because it is the point where the line

OP : x = a

meets the curve again.) We see in particular that there are no points of order 2 on E(𝔽_{2^{5}}). So the number N of points is odd: 5, 15, . . ..

iii. Hasse’s Theorem tells us that

|N − 33| ≤ 2\sqrt{32} = 8\sqrt{2}.

Since [8\sqrt{2}] = 11, this yields

22 ≤ N ≤ 44.

Thus

N = 25 or 35.

This leaves 3 possible cases:

ℤ/(25), ℤ/(35) and ℤ/(5) ⊕ ℤ/(5).

iv. Consider the action of the Frobenius automorphism

Φ : (x, y) ↦ (x^{2}, y^{2}) : E(𝔽_{2^{5}}) → E(𝔽_{2^{5}}).

The fixed points of this map are precisely the 5 points of E(𝔽_{2}). Moreover,

Φ^{5} = I.

Thus the group

⟨Φ⟩ = C_{5}

acts on the group on the curve; and the fixed elements under this action form a subgroup of order 5.

This last observation allows us to distinguish between the 3 cases. An automorphism θ of the group ℤ/(n) is completely determined by

θ(¯1) = ā.

Moreover, a must be invertible modn. It follows that

Aut(ℤ/(n)) = (ℤ/n)^{×}.

This group has ϕ(n) elements; and since

ϕ(35) = ϕ(5)ϕ(7) = 4 · 6 = 24,

the automorphism group of ℤ/(35) cannot contain an element of order 5; so this case is impossible. The group A = ℤ/(25) has just one subgroup B with 5 elements. If an automorphism

θ : A → A

has ker θ = B then im θ = B and so θ^{2} = 0, contradicting the assumption that θ is an automorphism. We are left with only 1 possibility; the group must be ℤ/(5)⊕ℤ/(5). [Although not necessary for this question, it is worth noting that we can regard the group ℤ/(5) ⊕ ℤ/(5) as a 2-dimensional vector space over the field 𝔽_{5}. Thus the automorphism group of this group is GL(2, 𝔽_{5}), the group of invertible 2 × 2 matrices over the field 𝔽_{5}. We can construct such a matrix by first choosing a non-zero vector for first column; this can be done in 5^{2} − 1 = 24 ways. Then any vector can be chosen for the second row, except for the 5 scalar products of the first row. This can be done in 5^{2} − 5 = 20 ways. It follows that the automorphism group in this case has 480 elements. By Sylow’s Theorem, the subgroups of order 5 are all conjugate; a typical one is formed by the matrices

(\begin{matrix}1 & a \\ 0 & 1 \end{matrix}) (a ∈ 𝔽_{5}).

It is readily verified that this automorphism subgroup leaves invariant a 1-dimensional subspace containing 5 vectors.]