MATH 470 Lecture 24

« previous | Tuesday, April 16, 2013 | next »

Recall

$\mathbb {F} _{p}$ , where $p$ is prime, represents a prime field
$\mathbb {F} _{q}$ , where $q$ is a prime power not a prime, represents a finite extension field.

Consider $\mathbb {F} _{27}$ realized as $\mathbb {F} _{3}\left[T\right]/\left\langle T^{3}+2T+1\right\rangle$ .

We need to check that $T^{3}+2T+1$ is irreducible (i.e. it has no non-trivial roots)

If it had a non-trivial factorization, it would be (linear) × (quadratic)

$t$	$t^{3}+2t+1$
0	1
1	1
2	1

Therefore there are no roots mod 3.

Therefore, $\mathbb {F} _{3}\left[T\right]/\left\langle T^{3}+2T+1\right\rangle$ is a realization of $\mathbb {F} _{3^{3}}=\mathbb {F} _{27}$

Inverses

What is ${\frac {1}{T+1}}$ in this realization of $\mathbb {F} _{27}$ ?

It would be the polynomial $p(T)\in \mathbb {F} _{3}\left[T\right]$ with $p(T)\,(T+1)=1$ .

This is equivalent to finding polynomials $p(T),q(T)\in \mathbb {F} _{3}\left[T\right]$ with $p(T)\,(T+1)+q(T)\,(T^{3}+2T+1)=1$ .

When working with integers, we had the extended Euclidean algorithm. We can still use it, but we need a few modifications:

${\begin{bmatrix}1&0\\0&1\\a(T)&b(T)\end{bmatrix}}\to {\begin{bmatrix}*(T)&u(T)\\*(T)&v(T)\\0&1\end{bmatrix}}$

Our goal is to make $a$ and $b$ smaller in degree (rather than absolute value, as we did with integers).

Example

To compute ${\frac {1}{T+1}}$ in the above realization of $\mathbb {F} _{27}$ , we do...

${\begin{bmatrix}1&0\\0&1\\T+1&T^{3}+2T+1\end{bmatrix}}\to {\begin{bmatrix}1&-T^{2}\\0&1\\T+1&-T^{2}+2T+1\end{bmatrix}}\to {\begin{bmatrix}1&-T^{2}+T\\0&1\\T+1&3T+1\end{bmatrix}}\to {\begin{bmatrix}1&-T^{2}+T-3\\0&1\\T+1&-2\end{bmatrix}}\to {\begin{bmatrix}1&2T^{2}+T\\0&1\\T+1&1\end{bmatrix}}$

Therefore, $(2T^{2}+T)\,(T+1)+(1)\,(T^{3}+2T+1)=1$ , and ${\frac {1}{T+1}}=2T^{2}+T$ in this $\mathbb {F} _{27}$ .

Note that there are possibly many distinct realizations of $\mathbb {F} _{q}$ : this is why the irreducible polynomial must be clarified!

Is $T^{3}+2T+1$ primitive over $\mathbb {F} _{3}$ ? (i.e. do the powers $1,T,T^{2},\ldots ,T^{26}=\mathbb {F} _{27}^{*}$ ?

What do we know about the order of $T$ in $\mathbb {F} _{27}^{*}$ .

Recall: the order of T in a field $\mathbb {F} _{q}$ would be the smallest $k$ with $T^{k}=1$ in $\mathbb {F} _{q}$

Lagrange's Theorem

Implies that the order of any $T\in \mathbb {F} _{q}^{*}$ must divide the cardinality (number of elements) of $\mathbb {F} _{q}^{*}$ .

The cardinality of $\mathbb {F} _{q}^{*}$ is $q-1$ , so ${\text{order}}\mid (q-1)$

For our realization of $\mathbb {F} _{27}$ , the order could be 1, 2, 13, or 26

order of $T$ is not 1 since $T\neq 1$ in this realization.
order of $T$ is not 2 since all 27 elements in this realization are distinct
order of $T$ is not 13 since $T^{13}=2$
Therefore, by elimination, the order of T is 26

Therefore, $T^{3}+2T+1$ is primitive over $\mathbb {F} _{3}$ :

Elements of $\mathbb {F} _{27}$ realized by $\mathbb {F} _{3}[T]/\left\langle T^{3}+2T+1\right\rangle$
$n$	$T^{n}$	$T^{n}{\pmod {T^{3}+2T+1}}{\pmod {3}}$
0	$1$	$0$
1	$T$	$T$
2	$T^{2}$	$T^{2}$
3	$T^{3}$	$-2T-1\equiv T+2$
4	$T^{4}$	$T^{2}+2T$
5	$T^{5}$	$(T+2)+2T^{2}\equiv 2T^{2}+T+2$
6	$T^{6}$	$(T+2)\,(T+2)\equiv T^{2}+T+1$
7	$T^{7}$	$(T+2)+T^{2}+T\equiv T^{2}+2T+2$
8	$T^{8}$	$(T+2)+2T^{2}+2T\equiv 2T^{2}+2$
9	$T^{9}$	$(T+2)^{3}\equiv (T+2)+2\equiv T+1$
10	$T^{10}$	$T^{2}+T$
11	$T^{11}$	$(T+2)+T^{2}\equiv T^{2}+T+2$
12	$T^{12}$	$(T+2)+T^{2}+2T\equiv T^{2}+2$
13	$T^{13}$	$(T+2)+2T\equiv 2$
14	$T^{14}$	$2T$
15	$T^{15}$	$2T^{2}$
16	$T^{16}$	$2(T+2)\equiv 2T+1$
17	$T^{17}$	$2T^{2}+T$
18	$T^{18}$	$2(T+2)+T^{2}\equiv T^{2}+2T+1$
19	$T^{19}$	$(T+2)+2T^{2}+T\equiv 2T^{2}+2T+2$
20	$T^{20}$	$2(T+2)+2T^{2}+2T\equiv 2T^{2}+T+1$
21	$T^{21}$	$2(T+2)+T^{2}+T\equiv T^{2}+1$
22	$T^{22}$	$(T+2)+T\equiv 2T+2$
23	$T^{23}$	$2T^{2}+2T$
24	$T^{24}$	$2(T+2)+2T^{2}\equiv 2T^{2}+2T+1$
25	$T^{25}$	$2(T+2)+2T^{2}+T\equiv 2T^{2}+1$
26	$T^{26}$	$2(T+2)+T\equiv 1$

In sage,

k = GF(3^3, 'T') for i,x in enumerate(k): print i,x

Elliptic Curves

Consider elliptic curve $E:y^{2}=x^{3}+x+1$ over $\mathbb {F} _{q}$ realized as $\mathbb {F} _{3}\left[9\right]/\left\langle T^{2}-2\equiv T^{2}+1\right\rangle$

First: what are the squares in (this) $\mathbb {F} _{9}$ ?

$x$ or $y$	$y^{2}$	$x^{3}+x+1$
$0$	$0$	$1$
$1$	$1$	$0$
$2$	$1$	$2$
$T$	$2$ *	$1$
$T+1$	$2T$	$0$
$T+2$	$T$	$2$
$2T$	$2$	$1$
$2T+1$	$T$	$0$
$2T+2$	$2T$	$2$

* Note: 2 has no square root mod 3, but ${\sqrt {2}}=\pm {T}$ in this $\mathbb {F} _{9}$

The points in this $\mathbb {F} _{9}$ of $E$ are:

$(0,\pm 1)$
$(1,0)$
$(2,\pm T)$
$(T+1,0)$
$(T+2,\pm T)$
$(2T,\pm 1)$
$(2T+1,0)$
$(2T+2,\pm T)$

There is also the point at infinity for a grand total of 16 points.

Hasse's Theorem

(1933)

If $E$ is any elliptic curve, over $\mathbb {F} _{q}$ with $n$ points, then

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

(conjectured by Emil Artin in his 1924 Ph.D. thesis, and ultimately led to P. Deligne winning a fields medal in 1974 for the riemann hypothesis for function fields)

This comes from the strange connection between finite fields and complex numbers in Genus 1

For our $E$ , we get that $n=16$ , so

${\begin{aligned}\left|16-(9+1)\right|&\leq 2{\sqrt {9}}\\\left|6\right|&\leq 2\cdot 3\end{aligned}}$

And this checks out.

Furthermore, Hasse's theorem implies that over $\mathbb {F} _{9}$ , the number of points must be between 4 and 16.

Addition Law

How does the addition law work here? (e.g. $(1,0)\oplus (2,T)=\Box$ ?)

Recall:

When adding two points $(x,y)\oplus (x',y')=(\mathbb {X} ,\mathbb {Y} )$ ,

Let $m={\begin{cases}{\frac {3x^{2}+1}{2y}}&x=x'\\{\frac {y'-y}{x'-x}}\end{cases}}$ , $\mathbb {X} =m^{2}-x-x'$ , and $\mathbb {Y} =m(x-\mathbb {X} )-y$