Project: Math 582b

Path: lectures / 2016-01-22 / 2016-01-22-finite-fields-second-part.sagews

Views: ²⁴⁹⁵

Finite Fields (more)

William Stein

Jan 22, 2016

Motivation: if you plan to ever do any computations over finite fields, today is going to make your life easier later. Simple as that.

Update on the "saga" of `GF(9)`.

# Recall
GF(9)   # expected "boom"

Error in lines 2-2
Traceback (most recent call last):
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 1, in <module>
  File "sage/structure/factory.pyx", line 364, in sage.structure.factory.UniqueFactory.__call__ (/projects/sage/sage-6.10/src/build/cythonized/sage/structure/factory.c:1245)
    key, kwds = self.create_key_and_extra_args(*args, **kwds)
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/finite_rings/constructor.py", line 479, in create_key_and_extra_args
    raise ValueError("parameter 'conway' is required if no name given")
ValueError: parameter 'conway' is required if no name given

# but...
GF(9,'a')

Finite Field in a of size 3^2

Then Nathann Cohen complained, which led to a huge thread and this ticket: http://trac.sagemath.org/ticket/19929

some discussion
a rude/mean comment from Nathann directed at me...
ticket closed
another ticket: http://trac.sagemath.org/ticket/17569

It looks like doing GF(9) might in the near future construct the quadratic subfield of $\bar{\FF}_{3}$ . Is this a good idea? What is $\bar{\FF}_p$ in Sage anyways?

Let's find out!


︠8f3f1450-1ae8-4790-a5b7-558f8d72240c︠

︠bf2cbbee-2532-4f1c-86a2-8ab261081aef︠

︠c64a8c9a-57a9-45dc-ab9b-2ca5705c1f8bi︠
%md
### The lattice of finite fields...?

The lattice of finite fields...?

F2.<a> = GF(3^2)
F3.<b> = GF(3^3)
a + b  # Sage doesn't magically do this...

Error in lines 3-3
Traceback (most recent call last):
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 1, in <module>
  File "sage/structure/element.pyx", line 1651, in sage.structure.element.RingElement.__add__ (/projects/sage/sage-6.10/src/build/cythonized/sage/structure/element.c:15852)
    return coercion_model.bin_op(left, right, add)
  File "sage/structure/coerce.pyx", line 1069, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (/projects/sage/sage-6.10/src/build/cythonized/sage/structure/coerce.c:9736)
    raise TypeError(arith_error_message(x,y,op))
TypeError: unsupported operand parent(s) for '+': 'Finite Field in a of size 3^2' and 'Finite Field in b of size 3^3'

Bummer?

No, not really...

There's no reason to expect a+b to make any sense in Sage, since we have two finite fields above with two different variable. Also, if the names were the same, it also wouldn't make sense, because then $a$ would be the generator of $\FF_{3^2}$ and $\FF_{3^3}$ simultaneously.

Incidentally, Magma doesn't care what you call things, and does make sense of adding the $a$ and $b$ defined above:

%magma    /* magma does */
F2<a> := FiniteField(3^2);
F3<b> := FiniteField(3^3);
a + b

$.1^297

Back to Sage...

At least we can do everything very explicitly and define embeddings.

F2.<a> = GF(3^2)
F3.<b> = GF(3^3)
F6.<c> = GF(3^6)

# Sadly, there is no "embeddings" command to produce all finite field morphisms from
# one field into another, which would be EASY to write (see below):
F2.embeddings

Error in lines 3-3
Traceback (most recent call last):
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 1, in <module>
  File "sage/structure/parent.pyx", line 859, in sage.structure.parent.Parent.__getattr__ (/projects/sage/sage-6.10/src/build/cythonized/sage/structure/parent.c:8131)
    attr = getattr_from_other_class(self, self._category.parent_class, name)
  File "sage/structure/misc.pyx", line 253, in sage.structure.misc.getattr_from_other_class (/projects/sage/sage-6.10/src/build/cythonized/sage/structure/misc.c:1667)
    raise dummy_attribute_error
AttributeError: 'FiniteField_givaro_with_category' object has no attribute 'embeddings'

# First get the roots of the defining polynomial of F2 in the field F6.
v = F2.polynomial().roots(ring=F6, multiplicities=False); v

[2*c^5 + 2*c^3 + c^2 + 2*c + 2, c^5 + c^3 + 2*c^2 + c + 2]

phi = Hom(F2, F6)(v[0])
phi

Ring morphism:
  From: Finite Field in a of size 3^2
  To:   Finite Field in c of size 3^6
  Defn: a |--> 2*c^5 + 2*c^3 + c^2 + 2*c + 2

phi(a)

2*c^5 + 2*c^3 + c^2 + 2*c + 2

def embeddings(E, F):
    """Compute all embeddings from the field E into the field F."""
    H = Hom(E,F)
    return [H(x) for x in E.polynomial().roots(ring=F, multiplicities=False)]

embeddings(GF(9,'a'), GF(3).algebraic_closure())

[Ring morphism:
  From: Finite Field in a of size 3^2
  To:   Algebraic closure of Finite Field of size 3
  Defn: a |--> z2, Ring morphism:
  From: Finite Field in a of size 3^2
  To:   Algebraic closure of Finite Field of size 3
  Defn: a |--> 2*z2 + 1]

def embeddings(E, F):
    """Compute all embeddings from the field E into the field F."""
    H = Hom(E,F)
    return [H(x) for x in E.polynomial().roots(ring=F, multiplicities=False)]


︠7b4d85da-3783-43f0-a61f-830bd03f640fs︠
def embeddings(E, F):
    """Compute all embeddings from the field E into the field F."""
    return list(Hom(E,F))

H = Hom(F2, F6)

H.list??

psi = embeddings(F3,F6)[0]
psi

Ring morphism:
  From: Finite Field in b of size 3^3
  To:   Finite Field in c of size 3^6
  Defn: b |--> 2*c^5 + 2*c^4

psi(b)

2*c^5 + 2*c^4

# Finally, compute the sum in F6:
%timeit phi(a) + psi(b)

625 loops, best of 3: 214 µs per loop

# this takes a lot of time though:
%timeit phi(a) + psi(b)

625 loops, best of 3: 146 µs per loop


︠01ab6c1c-f917-477f-9d1e-e81b9b13ff30︠

︠a9fbd2b8-aba5-4429-9a5d-3607d4e45f2a︠

︠99f6bdab-c412-47ad-8a70-5e6a25ab613d︠

︠73c45415-a554-4642-8e53-4bdade3949bbi︠
%md
So... at least it's possible to play around with different finite fields.

Though, as you might imagine, this "naive" appraoch can get very confusing and problematic!
What if you do some more computations, choosing embeddings, and end up with two different
ways to get from $\FF_{3^2}$ to $\FF_{3^{12}}$, say?  In a program it could happen very naturally,
and lead to subtle bugs.

So... at least it's possible to play around with different finite fields.

Though, as you might imagine, this "naive" appraoch can get very confusing and problematic! What if you do some more computations, choosing embeddings, and end up with two different ways to get from $\FF_{3^2}$ to $\FF_{3^{12}}$ , say? In a program it could happen very naturally, and lead to subtle bugs.



︠b17a9888-4313-4dba-b4d8-89ea1f0cdc9di︠
%md
However, Sage **does** support working in $\overline{\FF}_p$, which is possibly very nice and solves our problem in a
way that doesn't run into subtle bugs/contradictions if things get more complicated.

However, Sage does support working in $\overline{\FF}_p$ , which is possibly very nice and solves our problem in a way that doesn't run into subtle bugs/contradictions if things get more complicated.

Fbar = GF(3).algebraic_closure()
Fbar

Algebraic closure of Finite Field of size 3

# Heh, somebody should implement latex(Fbar) -- it would be so easy...
latex(Fbar)

\text{\texttt{Algebraic{ }closure{ }of{ }Finite{ }Field{ }of{ }size{ }3}}

QQ.algebraic_closure()

Algebraic Field

latex(QQ.algebraic_closure())

\overline{\QQ}

g2 = Fbar.gen(2); g2
g3 = Fbar.gen(3); g3
g2 + g3

z2
z3
z6^5 + 2*z6^4 + 2*z6^3 + z6^2 + 2*z6 + 1

%timeit g2 + g2

625 loops, best of 3: 385 µs per loop

a = Fbar.subfield(2)[0].0
%timeit a+a

625 loops, best of 3: 120 ns per loop

f = Fbar.subfield(2)[1]

f.inverse_image(g2)

Error in lines 1-1
Traceback (most recent call last):
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 1, in <module>
  File "sage/rings/morphism.pyx", line 884, in sage.rings.morphism.RingHomomorphism.inverse_image (/projects/sage/sage-6.10/src/build/cythonized/sage/rings/morphism.c:6716)
    raise NotImplementedError
NotImplementedError

(g2+g3).minpoly()

x^6 + x^4 + 2*x^3 + x^2 + x + 2

g2*g3

z6^5 + 2*z6^4 + z6^2 + 2

F6, f = Fbar.subfield(6)
F6
f

Finite Field in z6 of size 3^6
Ring morphism:
  From: Finite Field in z6 of size 3^6
  To:   Algebraic closure of Finite Field of size 3
  Defn: z6 |--> z6

f(F6.0)

z6

F6.0 + g2 + g3

z6^5 + 2*z6^4 + 2*z6^3 + z6^2 + 1


︠c90c734f-b557-4eb5-af3d-55c692a97a1e︠

︠356bae76-d01b-4c05-98e2-a3645e4c3d7ai︠
%md

**Exercise:** Whenever you try anything in software you should be very worried that the implementation sucks. You should run some basic benchmarks and compare with what you know. Never trust anything (especially do not use closed source software). Is Fbar slow or fast? Try some simple benchmarks right now.

Exercise: Whenever you try anything in software you should be very worried that the implementation sucks. You should run some basic benchmarks and compare with what you know. Never trust anything (especially do not use closed source software). Is Fbar slow or fast? Try some simple benchmarks right now.

# 1. Benchmark (using %timeit) adding/multiplying g2 with itself here:


︠6abd1508-10b0-4cae-acee-d0d6344437f4︠

︠434efb04-fe35-45fe-ae78-e71c374839e2︠

︠8f893607-5fcb-4eef-89b8-7806ac66490a︠
# 2. Benchmark (using %timeit) adding/multiplying g2 with g3 (which results in an element of F6):


︠82e39ef8-4cf2-4f18-881f-9bad5052781a︠

︠29fd60d0-7916-4cf9-b33e-6c598a1c5f0cs︠
# 3. CRITICAL: How does the benchmark in 2 compare to what we did above?


︠b09663ec-22bb-4cfc-bccc-e131bc14f677︠

︠d7b92340-6d2a-4962-96ee-42f00cdc29b2︠

︠c14d01f6-3482-493b-baec-77160b9e83c5i︠
%md
### How does $\overline{\FF}_p$ in Sage work?

The main idea is to use pseudo-conway polynomials, which are conway polynomials without the lexicographic condition.

**Definition:** Suppose $f_n$ is the minimal polynomial of a generator $a$ of $\FF_{p^n}^*$.  For $m<n$, let $a^r$ be the smallest power of $a$ that generators $\FF_{p^m}$, and let $f_m$ be the minimal polynomial of $a^r$.  Say that $f_n$ and $f_m$ are **compatible** of $f_m$ divides $f_n$.

We call $f_n$ a **pseudo-Conway polynomial** if it is compatible with $f_m$ for all $m<n$.  This means that you can very easily understand the subfields of $\FF_{p^n}$ and maps between them explicitly in terms of these polynomials.

Of course finding a pseudo-Conway polynomial isn't trivial.

To make it even harder, you could try to find a **Conway polynomial** which is the same as above, except you require all the $f_n$ to be lexicographically minimal.

How does $\overline{\FF}_p$ in Sage work?

The main idea is to use pseudo-conway polynomials, which are conway polynomials without the lexicographic condition.

Definition: Suppose $f_n$ is the minimal polynomial of a generator $a$ of $\FF_{p^n}^*$ . For $m<n$ , let $a^r$ be the smallest power of $a$ that generators $\FF_{p^m}$ , and let $f_m$ be the minimal polynomial of $a^r$ . Say that $f_n$ and $f_m$ are compatible of $f_m$ divides $f_n$ .

We call $f_n$ a pseudo-Conway polynomial if it is compatible with $f_m$ for all $m<n$ . This means that you can very easily understand the subfields of $\FF_{p^n}$ and maps between them explicitly in terms of these polynomials.

Of course finding a pseudo-Conway polynomial isn't trivial.

To make it even harder, you could try to find a Conway polynomial which is the same as above, except you require all the $f_n$ to be lexicographically minimal.


︠e0ca35f3-90a1-4fd1-bdd0-31cf583fa6c9︠

︠2ddb253f-203c-40ba-b462-f574ad94f7dai︠
%md
**Exercise:** Compare field creation time.

Exercise: Compare field creation time.

# 1. Something small using timeit (which might be very misleading?) -- just try changing 3 to something small
%timeit GF(3^6,'a')
%timeit GF(3).algebraic_closure().subfield(6)

625 loops, best of 3: 277 µs per loop
625 loops, best of 3: 641 µs per loop


︠eb39d710-adf6-4dee-8ac8-c80d90329e93︠
# 2. Something bigger: make p a prime with about 10 digits and the extension of degree 6.
p = next_prime(  # figure it out ...)
%time GF(p^6, 'a')
%time GF(p).algebraic_closure().subfield(6)



︠1a330fe0-1661-47e4-badc-46bd9afd3012︠

︠89f68132-6cfd-4a93-9021-eeabaadf2795︠

︠26f10393-3371-457b-bda0-12f76dcdc287︠
# 3. Something bigger: make p a prime with about 20 digits and the extension of degree 6.
︠c7d314c5-10de-4861-be96-6b1a30e9e753︠

︠fe452ff0-d8e0-471d-b1e2-07f172fcee6d︠

︠6b5cd754-2f5b-4f43-9be8-2db88cd50747︠

︠fec32b3c-556b-4169-aaf2-be88105c5706︠

︠aebfab28-bff1-4cee-bcc4-577bd7b40e47i︠
%md
Next time (again delayed): finite fields from prime ideals in rings of integers of number fields

Next time (again delayed): finite fields from prime ideals in rings of integers of number fields

︠3d1dc542-1f2a-4e1f-835a-c091fc613f51︠

Finite Fields (more)

William Stein

Jan 22, 2016

Update on the "saga" of `GF(9)`.

The lattice of finite fields...?

Bummer?

Back to Sage...

How does $\overline{\FF}_p$ in Sage work?

Product

Resources

Company

Finite Fields (more)

William Stein

Jan 22, 2016

Update on the "saga" of GF(9).

The lattice of finite fields...?

Bummer?

Back to Sage...

How does F‾p\overline{\FF}_pFp​ in Sage work?

Update on the "saga" of `GF(9)`.

How does $\overline{\FF}_p$ in Sage work?