\documentclass[10pt,a4paper]{article}
\usepackage{t1enc}
\usepackage{amsmath,amssymb,amsthm,amscd,graphicx}
\pagestyle{empty}
\usepackage[frenchb]{babel}
\usepackage[utf8]{inputenc}

\newcommand{\N}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\def\ds{\displaystyle}
\newcommand{\mathframe}[1]{\fbox{$#1$}}
\def\ima{\mathrm{Im}}

\topmargin-2.8cm
\oddsidemargin-2.4mm
\textwidth17.5cm
\textheight27cm
\parskip=3pt
\parindent=0pt

\pagestyle{empty}

\def\soluce#1{} % n'affiche pas les indications de solutions

\begin{document}



\noindent
M1 alg\`ebre effective  \hfill Polyn\^omes, GF\hfill UGA

\section{TD}
{\bf Exercice 1}
D\'eterminer les racines dans $\Z/p\Z$ de 
$P=x^4+x+1$ pour $p=5$ et $p=7$. Estimer le cout.

{\bf Exercice 2}
Soit $P$ le polyn\^ome $x^4+13x+1$. $P$ est-il squarefree
pour $p=7$~? $p=11$~?

{\bf Exercice 3}
Soit $P$ et $Q$ deux polyn\^omes \`a coefficients entiers. Montrer que
pour tout nombre premier $p$ ne divisant pas les coefficients
dominants de $P$ et $Q$, le degr\'e du pgcd de $P$ et $Q$ dans $\Q[X]$ est inf\'erieur ou
\'egal au degr\'e du pgcd de $P$ et $Q$ dans $\Z/p\Z[X]$.
En d\'eduire le PGCD de $x^4+x+1$ et $x^3+7x^2+7x+1$.

{\bf Exercice 4}
Soit $P=x^3+x+1$.
D\'eterminer l'inverse de $3x^2+x+1$ dans $\Z/11\Z[x]/P$

{\bf Exercice 5}
Soit $P$ le polyn\^ome $x^4+x+2$. $P$ est-il irr\'eductible modulo
3~?

{\bf Exercice 6}
Estimer le cout d'un test d'irr\'eductibilit\'e en fonction du degr\'e
du polyn\^ome [et de la taille de $p$].
D\'eterminer le cout moyen de construction d'un polyn\^ome
irr\'eductible de degr\'e $n$ modulo $p$.

{\bf Exercice 7}
\begin{enumerate}
\item D\'eterminer un polyn\^ome de degr\'e 4 irr\'eductible modulo 2.
Utiliser ce polyn\^ome pour g\'en\'erer la table d'addition d'un corps
$K$=GF(2,4).
\item D\'eterminer un g\'en\'erateur $g$
de votre corps*, et construire la table des puissances.
En d\'eduire une m\'ethode rapide pour multiplier, inverser, calculer une racine carr\'ee dans le
corps $K$.
\item R\'esoudre dans $K$ les \'equations $x^2+x+1=0$, $x^2+gx+g^2+g+1=0$, $x^2+gx+1=0$.. 
\end{enumerate}

{\bf Exercice 8}
Pour multiplier deux polyn\^omes
$P=a_nX^n+...+a_0$ et $Q=b_mX^m+...+b_0$ \`a coefficients dans un
corps $K=GF(p,d)$ extension de $\Z/p\Z$,
on se ram\`ene au produit de deux polyn\^omes \`a coefficients
dans $\Z/p\Z$. Soit
$M \in \Z/p\Z[X]$ un polyn\^ome irr\'eductible de degr\'e $d$
utilis\'e pour repr\'esenter les
\'el\'ements du corps $K$.
On pose~:
$$  p=a_n(X) X^{2nd}+...+a_0(X), \quad q=b_m(X) X^{2md}+...+b_0(X) $$
o\`u les $a_k, b_k$ sont des polyn\^omes de $\Z/p\Z[X]$ de degr\'e
$\leq d-1$. 
On effectue le produit $pq$ \`a l'aide d'un algorithme de
  multiplication efficace, \`a base de FFT.
On d\'ecompose par paquets de degr\'e de $2d$ en $2d$,
$pq=c_{n+m}(X) X^{2(n+m)d}+...+c_0(X)$ avec degr\'e de $c_k$ au plus
$2d-2$.\\
%\item On remplace les $c_k(X)$ par les restes $r_k$ de la division par $M$
Comment obtient-on $PQ$ en fonction des $c_k$~?
Quelle est la complexit\'e de cet algorithme~?

{\bf Exercice 9}
Effectuer le produit de $x^2+2x-1$ et $2x+1$ par FFT dans $\Z/5\Z[x]$.
% Division euclidienne rapide\\
% \verb|https://xcas.univ-grenoble-alpes.fr/forum/viewtopic.php?f=39&t=2497|

{\bf Exercice 10}
D\'eterminer la factorisation square-free de $x^7+x^6+x+1$ modulo 2.

{\bf Exercice 11}
Factoriser $x^5-x^4+x^3-x^2-1$ modulo 3.

{\bf Exercice 12}
D\'eterminer une racine carr\'ee de 5 modulo 101 en utilisant
l'algorithme de Cantor-Zassenhauss. Quel est le cout de la recherche
d'une racine carr\'ee par cette m\'ethode modulo un premier $p=1 \pmod
4$~?\\
D\'eterminer la factorisation de $x^2+3x+7$ mod 101 sans
chercher les racines de mani\`ere syst\'ematique.

{\bf Exercice 13}
Soit $A=x^4+1$ modulo $p=3$. V\'erifier qu'il poss\`ede 2 facteurs
de degr\'e $d=2$. Le factoriser en cherchant 
le PGCD de $A$ avec $T^{(p^d-1)/2}-1$ o\`u 
$T$ est un polyn\^ome al\'eatoire de degr\'e $2d-1=3$.


\section{TP}
{\bf Exercice 0}
V\'erifier/faire les parties calculatoires des exercices de TD.

{\bf Exercice 1}
Impl\'ementer l'algorithme de H\"orner pour \'evaluer un polynome
en un point. 
Modifier l'algorithme pour calculer le quotient. \'Ecrire
une fonction qui renvoie les facteurs de degr\'e 1
d'un polyn\^ome dans $\Z/p$ pour $p$ premier.

{\bf Exercice 2}
\'Ecrire une fonction renvoyant 1 si un polyn\^ome est squarefree
modulo $p$. Prolongement: renvoyer une factorisation partielle du polyn\^ome
(algorithme de Musser ou de Yun pour une factorisation squarefree).

{\bf Exercice 3}
\'Ecrire une fonction testant si un polyn\^ome est irr\'eductible
modulo $p$. Utiliser cette fonction pour construire un polyn\^ome
irr\'eductible de degr\'e $n$ modulo $p$ puis une repr\'esentation
du corps fini GF$(p,n)$

{\bf Exercice 4}
D\'eterminer les degrés des facteurs de $x^7+x^5+2x^4+x^3+x^2+2x+1$ modulo 5
et 7 (sans utiliser la commande factor). Quelle est la factorisation
sur $\Q$ de ce polyn\^ome~?

{\bf Exercice 5}
\'Ecrire une fonction renvoyant la factorisation ddf (distinct degree
factorization) d'un polyn\^ome squarefree modulo $p$. Tester sur
l'exemple de l'exercice pr\'ec\'edent.

{\bf Exercice 6}
Impl\'ementer le corps \`a 256 \'el\'ements de mani\`ere efficace
(en utilisant un entier 8 bits et une table).

{\bf Exercice 7}
Trouver des nombres premiers $p<2^{31}$ de la forme $1+k2^{25}$.
D\'eterminer une racine primitive $2^{25}$-i\`eme de l'unit\'e pour $p$.
A quelle condition peut-on calculer le produit de deux polyn\^omes
\`a coefficients dans $\Z/p\Z$ par FFT~?
Le faire sur un exemple en utilisant l'instruction \verb|fft| avec 3
arguments.\\
Soit $n<2^{31}$. Montrer qu'on peut effectuer un produit de polyn\^omes dont la somme
des degr\'es est $<2^{25}$ sur $\Z/n\Z$
en utilisant au plus 3 nombres premiers $p$ de ce type
et 3 produits par FFT. En d\'eduire une m\'ethode de multiplication de
polyn\^omes \`a coefficients entiers par FFT.

\end{document}
