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 {C}$ is actually a surface over two real dimensions.

For example, zero set of $x+y-1$ in $\mathbb {C}$ over $\mathbb {R}$ 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 {F} _{p}$ (also written $\mathrm {GF} (p)$) is defined to be a field with $p$ elements. For example, $\mathbb {F} _{p}=\mathbb {Z} /p\mathbb {Z}$.

Can $\mathbb {Z} /6\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 {F} _{q}$ with $q=p^{k}$ for any prime $p$ (and elliptic curves over $\mathbb {F} _{q}$).

Note: $\mathbb {F} _{q}\neq \mathbb {Z} /4\mathbb {Z}$

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

If $f\in \mathbb {F} _{p}\left[x\right]$, we derive

$\mathbb {F} _{p}\left[x\right]/\left\langle f\right\rangle$

as polynomials mod $f$.

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

$\mathbb {F} _{p}\left[x\right]/\left\langle f\right\rangle$ is just the polynomials in $\mathbb {F} _{p}\left[x\right]$ of degree less than that of $f$ with +, −, and × performed mod $f$.

Example

$\mathbb {F} _{2}\left[x\right]/\left\langle x^{2}+x+1\right\rangle =\left\langle 0,1,x,x+1\right\rangle$

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 {F} _{4}$

What if we chose $\mathbb {F} _{2}\left[x\right]/\left\langle x^{2}+1\right\rangle$?

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 {F} _{p}\left[x\right]$ irreducable iff $f=g\,h$ implies that $g\in \mathbb {F} _{p}$ or $h\in \mathbb {F} _{p}$. In other words, $f$ has no non-trivial factorization.

Example 1

$x^{2}-2$ is irreducable over $\mathbb {F} _{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 {F} _{3}$. But the squares in $\mathbb {F} _{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 {F} _{2}$: $x^{2}-2=x^{2}=x\,x$
• $\mathbb {F} _{7}$: $x^{2}-2=(x+3)(x+4)$

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

Example 2

$\mathbb {F} _{8}\left[x\right]$ can be realized as $\mathbb {F} _{2}\left[x\right]/\left\langle x^{3}+x+1\right\rangle$:

$\{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 {F} _{2^{135}}$	19,600
$\mathbb {F} _{2^{136}}=\mathbb {F} _{(2^{8})^{17}}$	7479
$\mathbb {F} _{239^{17}}$	5084

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

Primitivity

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

Example

$1+x+x^{3}$ is primitive over $\mathbb {F} _{2}\left[x\right]$. In particular, observe the powers of $x$ in $\mathbb {F} _{2}\left[x\right]/\left\langle x^{3}+x+1\right\rangle$

• $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 {F} _{8}$ and with an explicit generator for $\mathbb {F} _{8}^{*}$.

Note: $\mathbb {F} _{q}^{*}{=}\mathbb {F} _{q}\setminus \{0\}$ is comparable to $\left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$: 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 {F} _{2}\left[x\right]$ but not primitive

Sparsity

$x^{167}+x^{6}+1$ is irreducible over $\mathbb {F} _{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 {F} _{p}$?

Elliptic curves can be used to factor integers!

Factoring with Elliptic Curves

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

The number of elements in $\mathbb {F} _{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 {F} _{q}$,

$\left|n-(q+1)\right|\leq 2{\sqrt {q}}$

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