Lattices of compatibly embedded finite fields in Nemo/Flint

Luca De Feo, Hugues Randriambololona, Édouard Rousseau

Demonstrating the newly implemented lattices of compatibly embedded finite fields in Nemo.

Jupyter

In [ ]:
2^12

Nemo and Flint

  • Nemo is a computer algebra package for the Julia programming language [maintained by Hart, Hofmann, Fieker, Johansson, and others]
    • among many things, it includes a Flint wrapper
  • Flint is a number theory library for the C programming language [maintained by William Hart]

Nemo and Flint

A quick taste of Julia:

In [ ]:
function foo(L)
    m = L[1]    
    for i in 2:length(L)
        if m < L[i]
            m = L[i]
        end
    end
    return m
end
In [ ]:
L = [2, 4, 1, 5, 7, 11, 17, 3]
foo(L)

Nemo and Flint

In [ ]:
using Nemo

We can play with standard mathematical objects

In [ ]:
p = 13
k, x = FiniteField(p, 4, "x")
R, T = PolynomialRing(k, "T")
P = rand(R, 3)

The embedding problem

Example inspired by "On the powers of 2" [Granger, Kleinjung, Zumbrägel '14].

Let $P$ be an irreducible polynomial in $\mathbb F_{13^4}[T]$

In [ ]:
P = T^4+(8*x^3+6*x^2+12*x+2)*T^3+(8*x^3+3*x^2+2*x+2)*T^2+(2*x^3+5*x^2+7*x+12)*T+(3*x^3+4*x^2+6*x+5)
factor(P)

We really want to factor it in degree $2$ factors in $\mathbb F_{13^8}[U]$:

In [ ]:
K, y = FiniteField(p, 8, "y")
S, U = PolynomialRing(K, "U")
Q = S(P)
factor(Q)

The embedding problem

  • $f$ irreducible polynomial of degree $m$ in $\mathbb F_p[X]$
  • $g$ irreducible polynomial of degree $n$ in $\mathbb F_p[Y]$
  • $m\;|\;n$
  • $E = \mathbb F_p[X]/(f(X))$
  • $F = \mathbb F_p[Y]/(g(Y))$
$E\cong \mathbb F_{p^m} \hookrightarrow F\cong \mathbb F_{p^n}$
  • **Embedding problem:** how to compute the embedding from $E$ to $F$ ?

Description and evaluation

[Brieulle, De Feo, Doliskani, Flori, Schost '17]

Two steps:

  • Description: find $\alpha_1, \alpha_2$ such that:
    • $E = \mathbb F_p(\alpha_1)$
    • there exists an embedding $\phi:E\to F$ mapping $\alpha_1\mapsto\alpha_2$
  • Evaluation:
    • Compute $\phi(\gamma)\in F$ for $\gamma\in E$
    • Test if $\delta\in\phi(E)$ for $\delta\in F$
    • If $\delta\in\phi(E)$, compute $\phi^{-1}(\delta)\in E$

Description - naive algorithm

Context:

  • $E = \mathbb{F}_p[X]/(f)$
  • $F=\mathbb{F}_p[Y]/(g)$

Algorithm:

  • Find a root $\rho$ of $f$ in $F$
  • $\alpha_1 = \overline X$
  • $\alpha_2 = \rho$

Other algorithms exist:

  • [Lenstra '91]
  • [Allombert '02]
  • [Rains '96]
  • [Narayanan '18]

Description - naive algorithm

Compute an embedding with embed.

In [ ]:
E, x = FiniteField(13, 6, "x")
F, y = FiniteField(13, 12, "y")
ϕ = embed(E, F)

and evaluate it

In [ ]:
ϕ(x)

Some sanity checks

We can check that ϕ is indeed a morphism:

In [ ]:
a = rand(E)
b = rand(E)
ϕ(a^2 + b^7) == ϕ(a)^2 + ϕ(b)^7

and that the image of ϕ is in the subfield of $F$ with $13^6$ elements

In [ ]:
ϕ(a)^(13^6) == ϕ(a), ϕ(b)^(13^6) == ϕ(b)

The end ?

No!

The compatibility problem

Assume the user wants to use many extensions of $\mathbb F_p$:

The compatibility problem

Context:

  • $E$, $F$, $G$ fields
  • $E$ subfield of $F$ and $F$ subfield of $G$
  • $\phi_{E\hookrightarrow F}$, $\phi_{F\hookrightarrow G}$, $\phi_{E\hookrightarrow G}$ embeddings
$\phi_{F\hookrightarrow G}\circ\phi_{E\hookrightarrow F}\overset{?}{=}\phi_{E\hookrightarrow G}$

The compatibility problem

Solutions:

  • Conway polynomials [Parker '90], [Heath, Loehr '98]
    • used in Magma, Sage, PARI, ...
    • only practical with small finite fields
  • Bosma, Cannon and Steel framework [Bosma, Cannon, Steel '97]

Bosma, Cannon and Steel framework

  • Allows to work with arbitrary, user-defined finite fields
  • Allows to build the embeddings in arbitrary order
  • Used in MAGMA
  • based on the naive algorithm

Bosma, Cannon and Steel framework

  • Consider $\alpha$ such that $F=\mathbb{F}_p(\alpha)$
  • Take $\rho$ a root of $\phi_{E\hookrightarrow G}(\text{Minpoly}_E(\alpha))$
  • Map $\alpha\mapsto\rho$

Bosma, Cannon and Steel framework

It works with multiple subfields!

  • Consider $\alpha$ such that $F=\mathbb{F}_p(\alpha)$
  • Take $\rho$ a root of $\text{gcd}_i(\phi_{E_i\hookrightarrow G}(\text{Minpoly}_{E_i}(\alpha)))$
  • Map $\alpha\mapsto\rho$

The compatibility problem

We define some finite fields $E = \mathbb F_{p^2}$, $F = \mathbb F_{p^4}$ and $G = \mathbb F_{p^8}$.

In [ ]:
p = 5

E, x2 = FiniteField(p, 2, "x2")
F, x4 = FiniteField(p, 4, "x4")
G, x8 = FiniteField(p, 8, "x8")

and we compute the embeddings $\phi_{E\hookrightarrow F}$, $\phi_{F\hookrightarrow G}$, $\phi_{E\hookrightarrow G}$

In [ ]:
ϕE_F = embed(E, F)
ϕE_G = embed(E, G)
ϕF_G = embed(F, G)

The compatibility problem

Morphisms are compatible!

In [ ]:
a = rand(E)
ϕE_G(a) == (ϕF_G  ϕE_F)(a)

The compatibility problem II

$\phi_{G\hookrightarrow H}\circ\phi_{E\hookrightarrow G}\overset{?}{=}\phi_{F\hookrightarrow H}\circ\phi_{E\hookrightarrow F}$

The compatibility problem II

We create new finite fields

In [ ]:
G, x6 = FiniteField(p, 6, "x6")
H, x12 = FiniteField(p, 12, "x12")

and embeddings between them

In [ ]:
ϕE_G = embed(E, G)
ϕF_H = embed(F, H)
ϕG_H = embed(G, H)

The compatibility problem II

Morphisms are still compatible!

In [ ]:
a = rand(E)
(ϕG_H  ϕE_G)(a) == (ϕF_H  ϕE_F)(a)

Implicit conversion

We do not need to explicitly call embed. Standard object oriented conversion also works.

In [ ]:
k3, x3 = FiniteField(p, 3, "x3")
k24, x24 = FiniteField(p, 24, "x24")
In [ ]:
z = k24(x3)
In [ ]:
z^(p^3) == z
In [ ]:
k3(z)

Sections

We can also compute sections of morphisms.

In [ ]:
k7, x7 = FiniteField(p, 7, "x7")
k21, x21 = FiniteField(p, 21, "x21")
In [ ]:
f7_21 = embed(k7, k21)
In [ ]:
s21_7 = section(f7_21)

Sections

Sections give the preimage of an element if it is in the codomain of the embedding

In [ ]:
a = rand(k7)  
(s21_7  f7_21)(a) == a

And throw an error otherwise

In [ ]:
s21_7(x21)

Sections

This can also be called implicitly

In [ ]:
k7(k21(x7))
In [ ]:
k7(x21)

Behind the scenes

  • root finding is done by Flint (in C)
  • minimal polynomials are computed by Nemo (in Julia)
  • additionnal requirements of Bosma, Cannon and Steel framework are done in Nemo
  • (almost) all the time is spent in root finding
  • embedding evaluation is done via matrix-vector multiplication

More features planned

  • Vector space morphisms,
  • Algorithmic improvements,
  • more efficient framework using Lenstra/Allombert embedding algorithm as building block

Thank you!