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

- The slides are available as a
*Jupyter Notebook*on*Binder*at https://github.com/erou/Nemo-embeddings-demo - Press
`Alt + r`

to enter/quit slide mode - every cells are interactive so you can
**play around**

In [ ]:

```
2^12
```

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)
```

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)
```

*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)
```

- $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))$

- **Embedding problem:** how to compute the embedding from $E$ to $F$ ?

[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$

**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]

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)
```

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)
```

**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

**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]

- 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

- 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$

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$

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)
```

**Morphisms are compatible!**

In [ ]:

```
a = rand(E)
ϕE_G(a) == (ϕF_G ∘ ϕE_F)(a)
```

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)
```

**Morphisms are still compatible!**

In [ ]:

```
a = rand(E)
(ϕG_H ∘ ϕE_G)(a) == (ϕF_H ∘ ϕE_F)(a)
```

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)
```

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 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)
```

This can also be called implicitly

In [ ]:

```
k7(k21(x7))
```

In [ ]:

```
k7(x21)
```

- 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*

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