MATH 470 Lecture 23

« previous | Thursday, April 11, 2013 | next »

Going back to last time, we defined an elliptic curve over $k$ is the zero set (including the point at infinity) in $K^2$ of a polynomial $f\in K[x,y]$ with

1. the Newton polygon having exactly 1 point with integer coordinates in its interior.
2. a smooth curve $C$

Let's call this our 2^nd definition.

Let our first definition be the zero set of a polynmial in weierstrass normal form (including the point at infinity)

3^rd (classical) definition: A curve of genus one. So somehow, elliptic curves correspond to tori

So the number of interior lattice points in a Newton polygon is somehow related to the genus (under certain conditions).

What's a Genus

The classification of surfaces boils down to the number of holes (or number of handles, not that holes and handles are the same things...)

• Genus 0: Imagine a sphere
• Genus 1: Imagine a donut
• Genus 2: Handcuffs
• ...

A curve over $\mathbb{ℂ}$ is actually a surface over two real dimensions.

For example, zero set of $x+y-1$ in $\mathbb{ℂ}$ over $\mathbb{ℝ}$ is really just the zero set of the real part and the imaginary part.

Finite Fields

A finite field is any set of numbers closed on multiplicative inversion: all nonzero elements in the field have a multiplicative inverse in the same field.

For any prime $p$, ${\mathbb{𝔽}}_p$ (also written $\mathrm{G}\mathrm{F}(p)$) is defined to be a field with $p$ elements. For example, ${\mathbb{𝔽}}_p=\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}}$.

Can $\mathbb{\mathbb{Z}}/6\mathbb{\mathbb{Z}}$ be a field? No. (2 and 3 do not have inverses)

Finite fields need not have prime number of elements, only a prime power number of elements.

We'll study ${\mathbb{𝔽}}_q$ with $q=p^k$ for any prime $p$ (and elliptic curves over ${\mathbb{𝔽}}_q$).

Note: ${\mathbb{𝔽}}_q\ne \mathbb{\mathbb{Z}}/4\mathbb{\mathbb{Z}}$

We define ${\mathbb{𝔽}}_p\left[x\right]$ as the set of polynomials in $x$ with coefficients in ${\mathbb{𝔽}}_p$.

If $f\in {\mathbb{𝔽}}_p\left[x\right]$, we derive

${\mathbb{𝔽}}_p\left[x\right]/⟨f⟩$

as polynomials mod $f$.

(what's with these polynomials mod other polynomials?)

${\mathbb{𝔽}}_p\left[x\right]/⟨f⟩$ is just the polynomials in ${\mathbb{𝔽}}_p\left[x\right]$ of degree less than that of $f$ with +, −, and × performed mod $f$.

Example

${\mathbb{𝔽}}_2\left[x\right]/⟨x^2+x+1⟩=⟨0,1,x,x+1⟩$

Addition Table

+	0	1	x	x+1
0	0	1	x	x+1
1	1	0	x+1	x
x	x	x+1	0	1
x+1	x+1	x	1	0

Multiplication Table

×	0	1	x	x+1
0	0	0	0	0
1	0	1	x	x+1
x	0	x	x+1	1
x+1	0	x+1	1	x

Note: Reducing mod $x^2+x+1$ means you declare $x^2+x+1=0$, so $x^2=-(x+1)=x+1$

See that $\frac{1}{1}=1$, $\frac{1}{x}=x+1$, and $\frac{1}{x+1}=x$ are all well-defined, nonzero, invertible elements. Thus we have a realization of ${\mathbb{𝔽}}_4$

What if we chose ${\mathbb{𝔽}}_2\left[x\right]/⟨x^2+1⟩$?

Our multiplication table would be different:

Multiplication Table

×	0	1	x	x+1
0	0	0	0	0
1	0	1	x	x+1
x	0	x	1	x+1
x+1	0	x+1	x+1	0

Note that $\frac{1}{x+1}$ makes no sense.

Irreducibility

We call $f\in {\mathbb{𝔽}}_p\left[x\right]$ irreducable iff $f=gh$ implies that $g\in {\mathbb{𝔽}}_p$ or $h\in {\mathbb{𝔽}}_p$. In other words, $f$ has no non-trivial factorization.

Example 1

$x^2-2$ is irreducable over ${\mathbb{𝔽}}_3$.

Proof. Indeed, if $x^2-2$ had a non-trivial factorization (other than const × degree 2), then it must factor as $(\text{deg 1})(\text{deg 1})$.

Then

$x^2-2=c(x+a)(x+b)$

means that

$x^2-2$

has a root in

${\mathbb{𝔽}}_3$

. But the squares in

${\mathbb{𝔽}}_3$

are 0 and 1.

$x^2-2$

vanishes at neither, so

$x^2-2$

is irreducable.

Q.E.D.

However, $x^2-2$ is reducable over

• ${\mathbb{𝔽}}_2$: $x^2-2=x^2=xx$
• ${\mathbb{𝔽}}_7$: $x^2-2=(x+3)(x+4)$

Fact: ${\mathbb{𝔽}}_{p^k}$ can be realized as ${\mathbb{𝔽}}_p\left[x\right]/⟨f⟩$ for any irreducable $f\in {\mathbb{𝔽}}_p\left[x\right]$ of degree $k$.

Example 2

${\mathbb{𝔽}}_8\left[x\right]$ can be realized as ${\mathbb{𝔽}}_2\left[x\right]/⟨x^3+x+1⟩$:

$\{0,1,x,x+1,x^2,x^2+x,x^2+1,x^2+x+1\}$

Deciding Realizations

Which realization you use is very important in practice.

The Intel 8051 is a chip with 256 bytes of onboard RAM running at 12 MHz, used in some smart cards around 2000. This is an incredible hardware limitation, and operations can take a significant amount of time and power if the field realization is not chosen carefully.

Here's a table for the number of cycles needed to multiply two field elements:

Field	Number of Cycles
${\mathbb{𝔽}}_{2^{135}}$	19,600
${\mathbb{𝔽}}_{2^{136}}={\mathbb{𝔽}}_{(2^8{)}^{17}}$	7479
${\mathbb{𝔽}}_{239^{17}}$	5084

Upshot: Picking the right $f$ is key to going faster and saving power

Primitivity

We call an irreducable $f\in {\mathbb{𝔽}}_p\left[x\right]$ primitive iff $f$ has a primitive element for ${\mathbb{𝔽}}_{p^k}$ as one of its roots (generator).

Example

$1+x+x^3$ is primitive over ${\mathbb{𝔽}}_2\left[x\right]$. In particular, observe the powers of $x$ in ${\mathbb{𝔽}}_2\left[x\right]/⟨x^3+x+1⟩$

• $1$
• $x$
• $x^2$
• $x^3=x+1$
• $x^4=x\cdot x^3=x^2+x$
• $x^5=x\cdot x^4=x^2+x+1$
• $x^6=x\cdot x^5=x^2+1$
• $x^7=x\cdot x^6=1$

We've realized ${\mathbb{𝔽}}_8$ and with an explicit generator for ${\mathbb{𝔽}}_8^{*}$.

Note: ${\mathbb{𝔽}}_q^{*}={\mathbb{𝔽}}_q\setminus \{0\}$ is comparable to ${(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}})}^{*}$: nonzero elements of the referenced collection

Note: not all irreducible $f$ are primitive: $x^4+x^3+x^2+x+1$ is irreducable in ${\mathbb{𝔽}}_2\left[x\right]$ but not primitive

Sparsity

$x^{167}+x^6+1$ is irreducible over ${\mathbb{𝔽}}_2\left[x\right]$ and has only 3 terms. Therefore, powering is much faster.

For example, $x^{167}=x^6+1$. If we worked mod a non-sparse polynomial, we'd get $x^{167}=\text{MESS}$

So what's so good about curves over ${\mathbb{𝔽}}_p$?

Elliptic curves can be used to factor integers!

Factoring with Elliptic Curves

Classical factoring algorithms worked with arithmetic in ${\mathbb{𝔽}}_p^{*}$ or ${(\mathbb{\mathbb{Z}}/n\mathbb{\mathbb{Z}})}^{*}$ for some prime $p$. Working with elliptic curves over ${\mathbb{𝔽}}_p^{*}$ gives more flexibility

The number of elements in ${\mathbb{𝔽}}_p^{*}$ is $p-1$. The number of elliptic curves in the same field is $p+1+\text{wiggle}$

Hasse's Theorem

(1933)

If $n$ is the number of points on an elliptic curve over ${\mathbb{𝔽}}_q$,

$|n-(q+1)|\le 2\sqrt{q}$

And, for any such $n$, there is a curve over ${\mathbb{𝔽}}_q$ with that many points.