\documentclass{beamer}

\mode<presentation> {
  \usetheme{Montpellier}
  \setbeamercovered{transparent}
}

\usepackage[french]{babel} 
\usepackage[utf8]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\newcommand{\Cl}{\mathcal{C}\ell}
\newcommand{\N}{\mathcal{N}}
\renewcommand{\P}{\mathcal{P}}
\renewcommand{\O}{\mathcal{O}}
\newcommand{\p}{\mathfrak{p}}
\newcommand{\f}{\mathfrak{f}}
\renewcommand{\S}{\mathfrak{S}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\FF}{\mathbb{F}}
\renewcommand{\d}{\mathrm{d}}
\newcommand{\Gal}{\mathrm{Gal}}
\newcommand{\frob}[2]{\left(\frac{#1}{#2}\right)}
\newcommand{\val}{v}
%\renewcommand{\theorem}{}
\newtheorem{defi}{Définition}
\newtheorem{theorema}{Théorème}
\newtheorem{lemmaa}[theorem]{Lemme}
\newtheorem{remark}[theorem]{Remarque}
\newtheorem{princip}[theorem]{Principe}
\newtheorem{algorithm}[theorem]{Algorithme}
\renewcommand{\theorem}{\theorema}
\renewcommand{\lemma}{\lemmaa}
\newcommand{\kbd}[1]{\texttt{#1}}
\newcommand{\ida}{\mathfrak{a}}

\DeclareMathOperator{\Tr}{Tr}

\title{Finite fields with GP}
\date{16/01/2019}

\author{A.~Page}
\institute
{
  IMB\\
  Inria/Université de Bordeaux
}


\begin{document}

\begin{frame}
  \titlepage
$$\includegraphics[scale=0.3]{pari.png}$$
%TODO logo ODK
\end{frame}

\begin{frame}[fragile]{INTMOD's and POLMOD's}
You can perform operations in quotients with \kbd{Mod}.
\begin{verbatim}
? p = randomprime(2^100)
% = 792438309994299602682608069491
? a = Mod(2,p);
? type(a)
% = "t_INTMOD"
? a^(p-1)
% = Mod(1, 792438309994299602682608069491)
? a.mod == p
% = 1
? lift(a) \\lift to Z
% = 2
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{INTMOD's and POLMOD's}
You can perform operations in quotients with \kbd{Mod}.
\begin{verbatim}
? T = x^2+1;
? b = Mod(x+a, T);
? type(b)
% = "t_POLMOD"
? b^(p+1)
% = Mod(Mod(5,79243...69491),x^2+1)
? b.pol
% = Mod(1, 79243...69491)*x + Mod(2,79243...69491)
? b.mod == T
% = 1
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Creation of finite fields and FFELT's}
There is no finite field structure, finite fields are represented only by
elements.
\begin{verbatim}
? c = ffgen(3^8,'c) \\generator of F_3^8 as a field
% = c
? type(c)
% = "t_FFELT"
? c.p
% = 3
? c.mod \\defining polynomial, lifted to Z
% = c^8 + c^7 + 2*c^6 + c^3 + 2*c^2 + 2*c + 1
? polisirreducible(c.mod*Mod(1,3))
% = 1
? c.f \\degree over F_3
% = 8
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Creation of finite fields and FFELT's}
\begin{verbatim}
? d = c^9+1
% = 2*c^7 + 2*c^6 + 2*c^4 + 2*c^3 + c + 2
? d.pol
% = 2*c^7 + 2*c^6 + 2*c^4 + 2*c^3 + c + 2
? type(d.pol)
% = "t_POL"
\end{verbatim}

You can directly get an irreducible polynomial with \kbd{ffinit}.
\begin{verbatim}
? ffinit(3,5)
% = Mod(1,3)*x^5+Mod(1,3)*x^4+Mod(2,3)*x^3+Mod(1,3)
\end{verbatim}

You can also supply your own defining polynomial. We do not check for
irreducibility.
\begin{verbatim}
? ffgen(x^2+Mod(1,3))
% = x
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Creation from number fields}
You can create finite fields as residue fields of prime ideals.
\begin{verbatim}
? nf = nfinit(y^8-2*y^7+9*y^6-2*y^5+38*y^4-34*y^3\
?             +31*y^2-6*y+1);
? pr = idealprimedec(nf,2)[1]; [pr.e,pr.f]
% = [2, 2]
? g = nfmodpr(nf,y,pr)
% = y + 1
\end{verbatim}
  You can also initialise a structure with \kbd{modprinit} to avoid recomputing information.
\begin{verbatim}
? modpr = nfmodprinit(nf,pr);
? nfmodpr(nf,y^2+1,modpr)
% = y + 1
? nfmodprlift(nf,g+1,modpr) \\find a preimage
% = [0, 1, 0, 0, 0, 0, 0, 0]~
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Operations with elements}
  You can use many generic functions with finite field elements.
\begin{verbatim}
? [c,c+1;2*c,1]^-1
% = [...]
? d = random(c) \\random element in the field
% = c^5 + 2*c^4 + c^3 + 2*c^2 + c
? issquare(d)
% = 1
? trace(d) \\over F_3
% = Mod(2, 3)
? norm(d)
% = Mod(1, 3)
? minpoly(d^82)
% = Mod(1,3)*x^4+Mod(1,3)*x^2+Mod(1,3)*x+Mod(1,3)
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Operations with elements}
  You can use many generic functions with finite field elements.
\begin{verbatim}
? factor(x^5+x^3+c) \\variants factormodSQF
                      and factormodDDF
% = [x + (2*c^5 + c^4 + 2*c) 1]
    [x^2 + (c^7 + 2*c^6 + ... + c^2 + 2) 1]
    [x^2 + (2*c^7 + c^6 + ... + 2*c^2 + 1) 1]
? polrootsmod(x^7+x+c)
% = [c^7 + 2*c^6 + c^5 + c^3 + 2*c + 2,
     2*c^7 + c^6 + c^2 + 1]~
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Operations related to the multiplicative structure}
  Warning: the field generator is not necessarily a primitive root (group
  generator)!
\begin{verbatim}
? fforder(c)
% = 1640
? z = ffprimroot(c)
% = c^6 + c^5 + c^3 + c^2 + 2*c + 1
? fforder(z)
% = 6560
? n = fflog(c,z)
% = 6332
? c == z^n
% = 1
\end{verbatim}

  Reminder: there are corresponding functions on rings~$\ZZ/N\ZZ$: \kbd{znorder},
  \kbd{znprimroot}, \kbd{znlog}.
\end{frame}

\begin{frame}[fragile]{Curves}
  Elliptic curves operations and hyperelliptic curves point counting are
  available over finite fields.
\begin{verbatim}
? E = ellinit([c,1]);
? E.cyc \\structure of the group of points
% = [80, 80]
? ellissupersingular(E)
% = 1
? hyperellcharpoly(x^7+c*x+2) \\y^2 = x^7+c*+2
% = x^6 - 81*x^5 + ... + 282429536481
\end{verbatim}

  See \kbd{?12} for more!
\end{frame}


\begin{frame}[fragile]{Maps between finite fields}
  There is a structure for maps between finite fields.
\begin{verbatim}
? d = ffgen([3,24],'d)
% = d
? Mcd = ffembed(c,d); \\compute some embedding
? ffembed(d,c)
  ***   at top-level: ffembed(d,c)
  ***                 ^------------
  *** ffembed: domain error in ffembed: d is not a subfield of c
? c2 = ffmap(Mcd,c^5+c+1) \\apply the map
% = d^20 + 2*d^18 + ... + 2*d^5 + 1
? F = fffrobenius(d,8); \\8-th power of Frobenius
? ffmap(F, d) == d
% = 0
? ffmap(F, c2) == c2
% = 1
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Extending finite fields}
  You can construct extensions of finite fields defined by an irreducible
  polynomial with~\kbd{ffextend}.
\begin{verbatim}
? T = ffinit(3,5)
% = Mod(1,3)*x^5+Mod(1,3)*x^4+Mod(2,3)*x^3+Mod(1,3)
? [e,Mde] = ffextend(d, T, 'e);
? e.f
% = 120
? fforder(e)
% = 242
? ffmap(Mde, d)
% = ...
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Composing maps}
  You can compute the composition of maps:
  $\kbd{ffcompomap}(f,g) = f\circ g$.
\begin{verbatim}
? Mce = ffcompomap(Mde,Mcd);
? ffmap(Mce, c) == ffmap(Mde, ffmap(Mcd, c))
% = 1
? ffcompomap(F,Mcd) == Mcd
% = 1
? ffcompomap(F,F) == fffrobenius(d,16)
% = 1
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Preimages}
  You can compute the partial inverse of a map with~\kbd{ffinvmap}.
\begin{verbatim}
? Mdc = ffinvmap(Mcd);
? ffmap(Mdc, ffmap(Mcd, c^3+c+1))
% = c^3 + c + 1
? ffmap(Mdc, d)
% = [] \\sentinel value: no preimage
? Mec = ffcompomap(Mdc, ffinvmap(Mde));
? ffmap(Mec, ffmap(Mce, c))
? ffinvmap(fffrobenius(c,3)) == fffrobenius(c,5)
% = 1
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Relative extensions}
  Given a map between finite fields, we could compute the relative trace, norm,
  characteristic polynomial, a relative expression for elements of the larger
  field, etc.

  \medskip

  Which names / interface would you like to see?
\end{frame}

\end{document}