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, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_p} ?

Elliptic curves can be used to factor integers!

Factoring with Elliptic Curves

Classical factoring algorithms worked with arithmetic in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_p^*} or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( \mathbb{Z} / n \mathbb{Z} \right)^*} for some prime Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} . Working with elliptic curves over $\mathbb {F} _{p}^{*}$ gives more flexibility

The number of elements in $\mathbb {F} _{p}^{*}$ is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p-1} . The number of elliptic curves in the same field is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p+1+\text{wiggle}}

Hasse's Theorem

(1933)

If $n$ is the number of points on an elliptic curve over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_q} ,

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

And, for any such $n$, there is a curve over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_q} with that many points.