MATH 470 Lecture 24

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

Recall

• ${\mathbb{𝔽}}_p$, where $p$ is prime, represents a prime field
• ${\mathbb{𝔽}}_q$, where $q$ is a prime power not a prime, represents a finite extension field.

Consider ${\mathbb{𝔽}}_{27}$ realized as ${\mathbb{𝔽}}_3\left[T\right]/⟨T^3+2T+1⟩$.

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{𝔽}}_3\left[T\right]/⟨T^3+2T+1⟩$ is a realization of ${\mathbb{𝔽}}_{3^3}={\mathbb{𝔽}}_{27}$

Inverses

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

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

This is equivalent to finding polynomials $p(T),q(T)\in {\mathbb{𝔽}}_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:

$\left[\begin{array}{cc}1& 0\\ 0& 1\\ a(T)& b(T)\end{array}\right]\to \left[\begin{array}{cc}*(T)& u(T)\\ *(T)& v(T)\\ 0& 1\end{array}\right]$

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{𝔽}}_{27}$, we do...

$\left[\begin{array}{cc}1& 0\\ 0& 1\\ T+1& T^3+2T+1\end{array}\right]\to \left[\begin{array}{cc}1& -T^2\\ 0& 1\\ T+1& -T^2+2T+1\end{array}\right]\to \left[\begin{array}{cc}1& -T^2+T\\ 0& 1\\ T+1& 3T+1\end{array}\right]\to \left[\begin{array}{cc}1& -T^2+T-3\\ 0& 1\\ T+1& -2\end{array}\right]\to \left[\begin{array}{cc}1& 2T^2+T\\ 0& 1\\ T+1& 1\end{array}\right]$

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

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

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

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

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

Lagrange's Theorem

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

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

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

• order of $T$ is not 1 since $T\ne 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{𝔽}}_3$:

Elements of ${\mathbb{𝔽}}_{27}$ realized by ${\mathbb{𝔽}}_3[T]/⟨T^3+2T+1⟩$

$n$	$T^n$	$T^n(\mathrm{mod}{T}^3+2T+1)(\mathrm{mod}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{𝔽}}_q$ realized as ${\mathbb{𝔽}}_3\left[9\right]/⟨T^2-2\equiv T^2+1⟩$

First: what are the squares in (this) ${\mathbb{𝔽}}_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{𝔽}}_9$

The points in this ${\mathbb{𝔽}}_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{𝔽}}_q$ with $n$ points, then

$|n-(q+1)|\le 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{array}{rl}|16-(9+1)|& \le 2\sqrt{9}\\ \left|6\right|& \le 2\cdot 3\end{array}$

And this checks out.

Furthermore, Hasse's theorem implies that over ${\mathbb{𝔽}}_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)=◻$ ?)

Recall:

When adding two points $(x,y)\oplus (x^{\prime },y^{\prime })=(\mathbb{𝕏},\mathbb{𝕐})$,

Let $m=\{\begin{array}{ll}\frac{3x^2+1}{2y}& x=x^{\prime }\\ \frac{y^{\prime }-y}{x^{\prime }-x}\end{array}$, $\mathbb{𝕏}=m^2-x-x^{\prime }$, and $\mathbb{𝕐}=m(x-\mathbb{𝕏})-y$

So going back to our example, $(1,0)\oplus (2,T)$, we get

• $m=\frac{T-0}{2-1}=T$
• $\mathbb{𝕏}=T^2-1-2=T^2=2$
• $\mathbb{𝕐}=m(x-\mathbb{𝕏})-y=2T$

and $(1,0)\oplus (2,T)=(2,2T)$