\documentclass[a4paper,12pt]{amsart}
\usepackage{kbexo}


%%%%%%%%%%%%%%%%%%%%%
%% Alice's packages
%%%%%%%%%%%%%%%%%%%%%
\usepackage{xcolor}

%%%%%%%%%%%%%%%%%%%
%% Alice's macros
%%%%%%%%%%%%%%%%%%%
\newcommand{\comment}[1]{{\color{gray}#1}}

\def\pow{\^{}\hskip0pt}
\def\e{\varepsilon}
\def\a{\alpha}
\def\b{\beta}
\def\o{\omega}
\def\g{\gamma}
\def\s{\sigma}
\def\it{\til{\iota}}
\def\T{\Theta}
\def\t{\theta}

\course{Algèbre et calcul formel -- Agrégation}
\num{5}

\begin{document}
\exotitle[Extensions algébriques]

\exo[Corps de nombres]

\Q Définir l'anneau de polynôme {\tt Qx}$=\QM[x]$. Dans cet anneau, définir
le polynôme $P=x^2+3$, puis taper les commandes qui donnent les racines de
$P$ dans $\QM$, puis dans $\RM$, puis dans $\CM$.

\Q Exécuter les commandes suivantes.

\noindent{}{\tt K.<a>=NumberField(P)} (alors {\tt K} est le corps
$\QM(a)$, où $a$ est une racine de $P$).
\begin{verbatim}
  P.roots(K)
  Q = x^2+x+1
  Q.roots();Q.roots(K)
  Kx.<x> = PolynomialRing(K)
  factor(Kx(P))
  Q = x^5-x+1
  Q.is_irreducible()
  L.<b>=NumberField(Q)
  norm(b)
  parent(Q)
  Q = Qx(x^5-x+1); parent(Q)
  L.<b> = NumberField(Q)
  norm(b)
  b^10
  b.complex_embeddings()
\end{verbatim}
Expliquer les résultats sur la norme de $b$. Essayer ensuite les
fonctions {\tt minpoly(b)} et {\tt b.galois\_conjugates(L)}.

\Q Soit  $R=x^8+x^3+1\in\QM[x]$. Vérifier que {\tt R(b).lift()} donne le
reste de la division de $R$ par $Q$.

\noindent\comment{(Remarque: attention, ce n'est pas parce que cette méthode marche qu'il faut calculer vos divisions de polynômes comme ça... Pour calculer le reste de la division de $a$ par $b$, utiliser {\tt a\%b} (marche pour les entiers comme pour les polynômes).)}

\Q Soit $f=x^2-1\in\QM[x]$.
Si l'on essaie la commande {\tt NumberField} sur ce polynôme, on recevra un
message d'erreur, car $f$ n'est pas irréductible, et donc le quotient
$\QM[x]/(f)$ n'est pas un corps. Pour définir ce quotient, on peut utiliser
la commande
\begin{verbatim}
  Qxf.<t> = Qx.quotient(f)
\end{verbatim}
Alors, {\tt Qxf} est l'anneau quotient $\QM[x]/(f)$ et $t$ est la classe de $x$
dans ce quotient. Nous y reviendrons plus tard.

\Q\label{S3}
Soit $P=x^3-2x+2$. Vérifier que $P$ est irréductible dans $\QM[x]$. Soit $a$
une racine de $P$. Factoriser $P$ sur le corps $\QM(a)$. Montrer que le corps
de décomposition de $P$ est de degré $6$ sur $\QM$. Pour le voir, on aurait
pu également utiliser la fonction {\tt galois\_conjugates}.

\Q Soit $K=\QM(a)$. On peut définir une extension $L$ de $K$ en
exécutant la commande
{\tt L.<b>=K.extension(Q)}, où $Q$ est un polynôme irréductible de $K[x]$.
Définir ainsi le corps $L=K(\sqrt{-19})$, puis factoriser $P$ dans $L[x]$.

\Q Reprendre la question \ref{S3}) avec $P=x^3+2x^2-x-1$. Quel est le degré sur
$\QM$ du corps de décomposition de $P$?

\Q Soit $a$ une racine de $P$ et $P_a$ le polynôme minimal de $a+a^{-1}$. Quel sont les degrés possibles pour $P_a$? Utiliser Sage pour calculer $P_a$ et vérifier son degré.


\exo[Égalité de radicaux]
On veut démontrer l'identité \begin{equation}\label{equa}
(2^{1/3}-1)^{1/3}=(1/9)^{1/3}-(2/9)^{1/3}+(4/9)^{1/3}.
\end{equation}
\Q En utilisant les approximations numériques,
vérifier qu'elle est plausible.
\Q Soit $a=(2^{1/3}-1)^{1/3}$; calculer son polynôme minimal.
\Q En factorisant $x^3-1/9$ dans $\QM(a)$, exprimer $9^{-1/3}$ en fonction de
$a$. Faire de même avec $(2/9)^{1/3}$ et avec $(4/9)^{1/3}$. À l'aide des
expressions obtenues, vérifier l'égalité (\ref{equa}).

\vspace{3mm}
\noindent\textbf{Quizz.} Selon vous, est-ce que calculer le polynôme minimal d'un nombre algébrique est facile (on connaît un algorithme polynomial) ou difficile (le meilleur algorithme connu n'est pas polynomial) ?\\
\comment{(Remarque: vous pouvez essayer de calculer des polynômes minimaux d'éléments de la forme $2^{1/n}$ ou $2^{1/n}+3^{1/m}$ et faire augmenter $m$ et $n$ pour voir le temps que ça prend.)}

\exo[Corps finis]
\Q On peut définir $\FM_5=\ZM/5\ZM$  en utilisant
{\tt IntegerModRing(5)}, Mais il existe une façon directe de définir ces
corps. Pour $\FM_5$:

{\tt k = GF(5)}

\noindent{}Pour voir la liste des éléments du corps, taper :

{\tt k.list()}

\noindent{}Pour définir $\FM_{25}$, on tape la commande suivante.

{\tt k2.<t> = GF(25)}

Taper

{\tt k2; k2.list()}

\noindent{}On voit alors la liste des éléments de \texttt{k2}, comme
polynômes en $t$. Pour connaître le polynôme minimal de $t$, taper

{\tt k2.modulus()}

\noindent{}On peut aussi imposer un générateur du corps.
Exécuter les commandes suivantes.
\begin{verbatim}
  PR.<y> = PolynomialRing(GF(5))
  p = y^2+2; p.is_irreducible()
  k3.<b>=GF(25,modulus=p); k3
\end{verbatim}

\Q Vérifier que $P=x^4+x+1$ est irréductible dans $\FM_7[x]$
(on utilisera {\tt k=GF(7)} pour définir $\FM_7$). Soit $a$ la classe de $x$
dans $\FM_7[x]/(P)$ (pour définir $a$ et l'extension correspondante, on peut
utiliser {\tt k4.<a> = GF(7\pow4, modulus=P)}).

Cet élément $a$ est-il un générateur de $(\FM_7[x]/(P))^*$~? On peut pour
répondre utiliser la commande {\tt multiplicative\_order}.

\Q En utilisant {\tt multiplicative\_generator}, trouver un générateur
de $(\FM_7[x]/(P))^*$.

\Q Vérifier que $Q=x^4+x^3+1$ est irréductible dans $\FM_7[x]$. Soit $b$
la classe de $x$ dans $\FM_7[x]/(Q)$. Cet élément $b$ est-il un générateur de
$(\FM_7[x]/(P))^*$~?

\Q Ces deux corps $\FM_7[x]/(P)=\FM_7[a]$ et $\FM_7[x]/(Q)=\FM_7[b]$ sont
tous deux isomorphes à $\FM_{7^4}$. Factoriser $Q$ dans $\FM_7[a][x]$, puis
définir explicitement un isomorphisme $f$ de $\FM_7[b]$ dans $\FM_7[a]$.

\Q Soient $r_i$, $1\leq i\leq 4$, les racines de $Q$ dans $\FM_7[a]$.
Vérifier que 
$$\set{r_i \colon 1\leq i \leq 4}=\set{r_1^{7^i} \colon 0\leq i \leq 3}.$$
Expliquer ce fait.

\Q Vérifier que $b^2+1$ engendre $\FM_7[b]^*$. Il suit que $f(b^2+1)$
engendre $\FM_7[a]^*$; le vérifier.

\Q En utilisant votre fonction FFT du TD 4,
programmer la multiplication
de deux polynômes de $\mathbb F_{3^4}[x]$ de degrés strictement inférieurs
à $8$.
\comment{(Remarque: pour multiplier deux polynômes de degré $ < 8$, on doit prendre $n = 16$ dans la FFT car le degré du produit peut aller jusqu'à $14$.)}

\noindent Pouvez-vous généraliser votre fonction à la multiplication de polynômes de degrés strictement inférieurs à $16$ ? Si ça ne marche pas, expliquer pourquoi.


\Q Écrire un programme qui, étant donnés un nombre premier $p$,
un polynôme $P$ de $\FM_p[x]$ irréductible de degré $n$, et la
factorisation de $p^n-1$, donne un générateur de $\big(\FM_p[x]/(P)\big)^*$.

\misctitle{Indication} Soit $G$ un groupe cyclique d'ordre $n$ et
soit
$$n=\prod_{i=1}^rp_i^{e_i}$$
la décomposition de $n$ en un produit de facteurs premiers (où les $p_i$ sont
deux à deux distincts et où $e_i>0$ pour tout $i$). Soit $g$ un élément de
$G$. Alors $g$ engendre $G$ si et seulement si pour tout $i$,
on a
$g^{\frac np_i}\ne1.$ On peut prendre des éléments dans $G$ au hasard et tester
ce fait. 

Une autre manière de faire est de construire des éléments $g_i$
d'ordre~$p_i^{e_i}$. Alors,
$$g=\prod_{i=1}^rg_i$$
est d'ordre $n$. Pour construire $g_i$, on choisit au hasard un élément
$h$ dans $G$. Si $h^{n/p_i}\ne1$, alors $g_i=h^{n/p_i^{e_i}}$ convient.
\end{document}
