<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[a4paper,12pt]{article}

\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amssymb,amsthm,amsmath,amsfonts,mathrsfs}
\newtheoremstyle{custom}%    &lt;name&gt;
{\topsep}%   &lt;space above&gt;
{\topsep}%   &lt;space below&gt;
{\normalfont}%  &lt;body font&gt;
{}%          &lt;indent amount&gt;
{\bfseries}% &lt;Theorem head font&gt;
{.}%         &lt;punctuation after theorem head&gt;
{\newline}%  &lt;space after theorem head&gt; (default .5em)
{}%          &lt;Theorem head spec&gt;
\theoremstyle{custom}
\usepackage{textcomp}
\usepackage{bbm}
\usepackage{geometry}
\usepackage{mathrsfs}
\usepackage{enumitem}
\usepackage{csquotes}
\usepackage{esvect}       % Pour des vecteurs 
\usepackage{hyperref}      %Pour des liens hypertexte !
\hypersetup{
	% backref=true,    %permet d'ajouter des liens dans...
	% pagebackref=true,%...les bibliographies
	% hyperindex=true, %ajoute des liens dans les index.
	colorlinks=true, %colorise les liens
	%     breaklinks=true, %permet le retour Ã&nbsp; la ligne dans les liens trop longs
	%     urlcolor= blue,  %couleur des hyperliens
	%     linkcolor= black, %couleur des liens internes
	%     linktoc	=all,	%defines which part of an entry in the table of contents is made into a link
	%     citecolor=black,	%color of citation links (bibliography)
	%     filecolor=black,	%color of file links
	% bookmarks=true,  %crÃ©Ã© des signets pour Acrobat
	bookmarksopen=true,            %si les signets Acrobat sont crÃ©Ã©s,
	%les afficher complÃ¨tement.
	pdftitle={M1 algÃ¨bre effective}, %informations apparaissant dans
	pdfauthor={Samuel Le Fourn},     %dans les informations du document
}
\frenchspacing



\newtheorem{thm}{ThÃ©orÃ¨me}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollaire}
\newtheorem*{thmsansnom}{ThÃ©orÃ¨me}
\newtheorem*{propsansnom}{Proposition}
\newtheorem{lem}[thm]{Lemme}



\theoremstyle{custom}
\newtheorem{defi}[thm]{DÃ©finition}
\newtheorem{rem}[thm]{Remarque}
\newtheorem{exe}[thm]{Exemple}
\newtheorem{exocours}[thm]{Exercice de cours}
\newtheorem{exerciseaux}[thm]{Exercice}
%\newenvironment{exo}{\begin{exerciseaux}\leavevmode\par}{\end{exo}}
\newtheorem{exo}[thm]{Exercice}

\def\R{\mathbb{R}}
\def\C{\mathbb{C}}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\F{\mathbb{F}}
\def\1{\mathbbm{1}}
\def\Ncal{\mathcal{N}}

\DeclareMathOperator{\pgcd}{pgcd}
\DeclareMathOperator{\ppcm}{ppcm}

\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Inn}{Inn}
\DeclareMathOperator{\id}{id}
\newcommand{\Ker}{\operatorname{Ker}}

\setlist{noitemsep}
\setlist[1]{labelindent=\parindent} % &lt; Usually \setlist[itemize]{leftmargin=*}
%d\setlist[itemize]{label = ($(\arabic*)$)}
\setlist[enumerate]{label = ($\alph*$)}



%%%%%%%%%%%%%%%%%%
% Alphabet Grec  %
%%%%%%%%%%%%%%%%%%
\renewcommand{\a}{\alpha}
\renewcommand{\b}{\beta}
\newcommand{\g}{\gamma}
\renewcommand{\d}{\delta}
\newcommand{\e}{\epsilon}
\newcommand{\f}{\varphi}
\renewcommand{\l}{\lambda}
\renewcommand{\k}{\kappa}
\newcommand{\m}{\mu}
\newcommand{\n}{\nu}
\renewcommand{\o}{\omega}
\renewcommand{\r}{\rho}
\newcommand{\s}{\sigma}
\renewcommand{\t}{\tau}
\newcommand{\z}{\zeta}
\newcommand{\D}{\Delta}
\newcommand{\G}{\Gamma}




%%%%%%%%%%%%%%%%%%%%
% Alphabet gothique%
%%%%%%%%%%%%%%%%%%%%
\newcommand{\ga}{{\mathfrak{a}}}
\newcommand{\gA}{{\mathfrak{A}}}
\newcommand{\gb}{{\mathfrak{b}}}
\newcommand{\gB}{{\mathfrak{B}}}
\newcommand{\gc}{{\mathfrak{c}}}
\newcommand{\gC}{{\mathfrak{C}}}
\newcommand{\gd}{{\mathfrak{d}}}
\newcommand{\gD}{{\mathfrak{D}}}
\newcommand{\gI}{{\mathfrak{I}}}
\newcommand{\gm}{{\mathfrak{m}}}
\newcommand{\gn}{{\mathfrak{n}}}
\newcommand{\go}{{\mathfrak{o}}}
\newcommand{\gO}{{\mathfrak{O}}}
\newcommand{\gp}{{\mathfrak{p}}}
\newcommand{\qg}{{\mathfrak{q}}}
\newcommand{\gP}{{\mathfrak{P}}}
\newcommand{\gQ}{{\mathfrak{Q}}}
\newcommand{\gq}{{\mathfrak{q}}}
\newcommand{\gR}{{\mathfrak{R}}}
\newcommand{\gS}{{\mathfrak{S}}}
\newcommand{\gJ}{{\mathfrak{J}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Alphabet calligraphique %
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\Acal}{{\mathcal A}}
\newcommand{\Bcal}{{\mathcal B}}
\newcommand{\Ccal}{{\mathcal C}}
\newcommand{\Dcal}{{\mathcal D}}
\newcommand{\Ecal}{{\mathcal E}}
\newcommand{\Fcal}{{\mathcal F}}
\newcommand{\Gcal}{{\mathcal G}}
\newcommand{\Hcal}{{\mathcal H}}
\newcommand{\Ical}{{\mathcal I}}
\newcommand{\Jcal}{{\mathcal J}}
\newcommand{\Kcal}{{\mathcal K}}
\newcommand{\Lcal}{{\mathcal L}}
\newcommand{\Mcal}{{\mathcal M}}
\newcommand{\Ocal}{{\mathcal O}}
\newcommand{\Pcal}{{\mathcal P}}
\newcommand{\Qcal}{{\mathcal Q}}
\newcommand{\Rcal}{{\mathcal R}}
\newcommand{\Scal}{{\mathcal S}}
\newcommand{\Tcal}{{\mathcal T}}
\newcommand{\Ucal}{{\mathcal U}}
\newcommand{\Vcal}{{\mathcal V}}
\newcommand{\Wcal}{{\mathcal W}}
\newcommand{\Xcal}{{\mathcal X}}
\newcommand{\Ycal}{{\mathcal Y}}
\newcommand{\Zcal}{{\mathcal Z}}

%%%%%%%%%%%%%%%%%%%%
% Alphabet en gras %
%%%%%%%%%%%%%%%%%%%%
\newcommand{\ab}{\mathbf{a}}

%%%%%%%%%%%%%%%%%%%%
% Ensembles usuels %
%%%%%%%%%%%%%%%%%%%%
\renewcommand{\P}{\mathbb{P}}
\newcommand{\Fp}{{\mathbb{F}_{\! p}}}
\newcommand{\A}{{\mathbb{A}}}
\newcommand{\T}{{\mathbb{T}}}

%%%%%%%%%%%%%%%%%%%%%
% OpÃ©rateurs usuels %
%%%%%%%%%%%%%%%%%%%%%
\newcommand{\Card}{\operatorname{Card}}
\newcommand{\Crit}{\operatorname{Crit}}
\renewcommand{\div}{\operatorname{div}}
\newcommand{\Div}{\operatorname{Div}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\Gal}{\operatorname{Gal}}
\newcommand{\SL}{\operatorname{SL}}
\newcommand{\Id}{\operatorname{Id}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\Proj}{\operatorname{Proj}}
\newcommand{\Spec}{\operatorname{Spec}}
\newcommand{\Borel}{\operatorname{Borel}}
\newcommand{\Stab}{\operatorname{Stab}}
\newcommand{\Cart}{\operatorname{Cart}}
\newcommand{\Cot}{\operatorname{Cot}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\cl}{\operatorname{cl}}
\newcommand{\gr}{\operatorname{gr}}
\newcommand{\init}{\operatorname{in}}
\newcommand{\PGL}{\operatorname{PGL}}
\newcommand{\PSL}{\operatorname{PSL}}
\newcommand{\Der}{\operatorname{Der}}
\newcommand{\num}{\operatorname{num}}
\renewcommand{\Re}{\operatorname{Re}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\Jac}{\operatorname{Jac}}
\newcommand{\Vect}{\operatorname{Vect}}
\newcommand{\car}{\operatorname{car}}
\newcommand{\Sp}{\operatorname{Sp}}
\newcommand{\Pic}{\operatorname{Pic}}
\newcommand{\carac}{\textrm{char}}
\newcommand{\Tr}{\operatorname{Tr}}
\renewcommand{\mod}{\, \operatorname{mod} \,}
\newcommand{\Frac}{\operatorname{Frac}}
\newcommand{\preuve}{\textcolor{blue}{$^{(P)}$}}
\newcommand{\Frob}{\operatorname{Frob}}
\renewcommand{\pgcd}{\operatorname{pgcd}}
%%%%%%%%%%%
% FlÃ¨ches %
%%%%%%%%%%%
\newcommand{\mt}{\mapsto}	
\newcommand{\lmt}{\longmapsto}
\newcommand{\ra}{\rightarrow}
\newcommand{\lra}{\longrightarrow}
\newcommand{\La}{\Leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\Lra}{\Leftrightarrow}
\newcommand{\Llra}{\Longleftrightarrow}

\newcommand{\dessin}{\textcolor{green}{(D)}}

%%% Commandes spÃ©cifiques Ã&nbsp; la gÃ©omÃ©trie affine %%%%
%\newcommand{Evect}{\overrightarrow{E}}
%\newcommand{Fvect}{\overrightarrow{F}}
%\newcommand{uvect}{\overrightarrow{u}}
%\newcommand{vvect}{\overrightarrow{v}}



%%%%%%%%%%%%%%%%%%
% Macros utiles %%
%%%%%%%%%%%%%%%%%%

\newcommand{\fonction}[5]{\begin{array}{c|ccl}           % Pour Ã©crire une fonction en environnement display : le nom puis espaces de dÃ©part et d'arrrivÃ©e, puis argument et rÃ©sultat
		#1: &amp; #2 &amp; \longrightarrow &amp; #3 \\
		&amp; #4 &amp; \longmapsto &amp; #5 \end{array}}


\newcommand{\fonctionsansnom}[4]{\begin{array}{ccl}      % La mÃªme sans le nom de la fonction Ã&nbsp; mettre
		#1 &amp; \lra &amp; #2 \\\
		#3 &amp; \lmt &amp; #4 
\end{array}}


\newtheorem{enonce}[thm]{Exercice}%[section]
\newenvironment{Ex}[0]{\begin{enonce}\rm}{\bigskip \end{enonce}}
%\newtheorem{theoreme}{Th\'eor\`eme}%[section]



\geometry{top=2cm, bottom=2cm}
\begin{document}
	\newgeometry{top=1cm,bottom=2cm,left=2cm,right=2cm}
	\noindent {\large \textsc{UniversitÃ© Grenoble Alpes \hfill M1 \\
			\hfill M1 AlgÃ¨bre effective \hfill 2024-2025}} \\
	\hrule
	\bigskip

	\begin{center}
	\textbf{\Large IrrÃ©ductibilitÃ© et factorisation de polynÃ´mes dans $\F_p$}
\end{center}
\medskip


\section{Exercices}
Ici, $p$ est partout un nombre premier.
	
	\begin{exo}[Recherche de racines]
		\label{ex:racinesdansFp}
		
		Soit $P \in \F_p[X]$. 
		\begin{enumerate}
\item Rappeler pourquoi $P$ a les mÃªmes racines dans $\F_p$ que $\pgcd(P,X^p-X)$ (voir le TD PGCD si nÃ©cessaire)
\item Donner les racines de $P$ dans $\F_p$ avec $P = X^4 + X + 1$ et $p=5$ ou 7.
\item Quel est le coÃ»t du calcul dans le pire cas avec $P$ de degrÃ© $n$ dans $\F_p[X]$ ?
	\end{enumerate}
	\end{exo}

\begin{exo}[IrrÃ©ductibilitÃ© d'un polynÃ´me au cas par cas]
	
	Soit $P = X^4 + X + 2 \in \Z[X]$. $P$ est-il irr\'eductible modulo
	3~? modulo 5 ?
\end{exo}


\begin{exo}[CoÃ»t moyen de recherche de polynÃ´me irrÃ©ductible]
	\begin{enumerate}
		\item[]
		\item En utilisant le cours, rappeler le coÃ»t d'un test d'irrÃ©ductibilitÃ© de $P \in \F_p[X]$ unitaire en fonction de $p$ et $n = \deg P$.
		\item Encore avec le cours, rappeler la proportion asymptotique de polynÃ´mes irrÃ©ductibles unitaires parmi les polynÃ´mes unitaires de degrÃ© $n$.
		\item En dÃ©duire un algorithme probabiliste de recherche de polynÃ´me irrÃ©ductible de degrÃ© $n$ dans $\F_p[X]$, et donner le coÃ»t moyen de cet algorithme.
	\end{enumerate}
\end{exo}

\begin{exo}[Construction explicite de $\F_{16}$]	
	\begin{enumerate}
		\item[]
		\item  D\'eterminer un polyn\^ome de degr\'e 4 irr\'eductible dans $\F_2[X]$.
		Utiliser ce polyn\^ome pour g\'en\'erer la table d'addition d'un corps
		$K$ de taille 16 (notÃ© \verb!GF(2,4)! dans Xcas).
		\item DÃ©terminer un gÃ©nÃ©rateur $g$ de $K^*$, et construire la table des puissances. 
		\item Avec cette table, donner une mÃ©thode 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}
\end{exo}

\begin{exo}[Puissance $p$-iÃ¨me dans les anneaux de polynÃ´mes en caractÃ©ristique $p$]
	\begin{enumerate}
		\item[]
		\item Rappeler pourquoi pour tout $x \in \F_p$, $x^p = x$.
		\item Dans tout anneau commutatif unitaire $A$ tel que $p \cdot 1_A = 0$ (on parle d'anneau de caractÃ©ristique $p$), montrer que $\Frob_A : x \mt x^p$ est encore un morphisme d'anneaux
		\item Pour tout $P \in \F_p[X]$, montrer que $P^p = P(X^p)$.
		\item RÃ©ciproquement, montrer que si $K$ est un corps fini de caractÃ©ristique $p$, avec les injections canoniques,
		\[
		\F_p[X] = \{ P \in K[X] \, | \, P(X^p) = \Frob_{K[X]}(P) = P^p \}.
		\]
	\end{enumerate}
\end{exo}


\begin{exo}[Factorisation squarefree (SQF) dans les corps finis]
	\label{exo:factorSQF}
	L'algorithme de Yun vu pour $\Q[X]$ ne fonctionne pas tel quel en caractÃ©ristique $p$, mais voici comment nÃ©anmoins trouver la factorisation sqf (squarefree) d'un polynÃ´me $P \in \F_p[X]$. 
	
	On pose $P = Q R$ avec $Q$ (resp. $R$) le produit des facteurs irrÃ©ductibles de $P$ de multiplicitÃ© multiple de $p$ (resp. premiÃ¨re Ã&nbsp; $p$), avec la mÃªme multiplicitÃ© que dans $P$, et on cherche d'abord Ã&nbsp; calculer $Q$ et $R$ connaissant $P$.
	
	\begin{enumerate}
		 \item Rappeler pourquoi $P$ est sans facteurs carrÃ©s si et seulement si  $\operatorname{pgcd}(P,P')=1$.
		
		\item Montrer que $\operatorname{pgcd}(P,P') = P$ si et seulement si $P$ est une puissance $p$-iÃ¨me dans $\F_p[X]$. 
		
		\item Montrer que $P' = Q R'$, et en dÃ©duire que $\operatorname{pgcd}(P,P') = Q \operatorname{pgcd}(R,R')$.
		
		\item En dÃ©duire comment calculer successivement $R/\pgcd(R,R')$, $R$, puis $Q$.
		
		\item Montrer que l'algorithme de Yun s'applique tel quel Ã&nbsp; $R$.
		
		\item Enfin, en Ã©crivant $Q = A^p$ pour un certain $A \in \F_p[X]$, montrer qu'on peut donner la factorisation sqf sqf de $P$ par rÃ©currence sur le degrÃ©.
		
		\item Appliquer cet algorithme pour calculer la factorisation square-free de $X^7+X^6+X+1$ modulo 2.
	\end{enumerate}
\end{exo}


\begin{exo}[Factorisation Ã&nbsp; degrÃ©s distincts (DDF)]
	\label{exo:factorDDF}
	Soit $P \in \F_p[X]$ de degrÃ© $n$, on cherche Ã&nbsp; Ã©crire 
	\[
	P = \prod_{k=1}^n P_k
	\]
	oÃ¹ $P_k$ est le produit des facteurs irrÃ©ductibles de $P$ de degrÃ© exactement $k$ (avec leur multiplicitÃ©).
	
\begin{enumerate}
	\item Montrer avec le cours que pour tout $k \leq n$, $\operatorname{pgcd}(P,X^{p^k}-X) = \prod_{d|k} P_d$. 
	\item Rappeler comment calculer efficacement ces pgcd, quel est le coÃ»t total ?
	\item En dÃ©duire comment calculer chacun des $P_k$. 
\end{enumerate}
\end{exo}
\begin{exo}[PGCD de polynÃ´mes Ã&nbsp; coefficients entiers]
	Soit $P$ et $Q$ deux polyn\^omes \`a coefficients entiers. 
	
	
	\begin{enumerate}
		\item 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]$.
		\item 	En d\'eduire le PGCD de $X^4+X+1$ et $X^3+7X^2+7X+1$ dans $\Z[X]$.
	\end{enumerate}

\end{exo} 

\begin{exo}[Algorithme de Cantor-Zassenhaus]
	\label{exo:algoCZ}
	Ici, on suppose $p&gt;2$, on cherche Ã&nbsp; factoriser un polynÃ´me $P \in \F_p[X]$ de degrÃ© $n$.
	\begin{enumerate}
		\item Avec les exercices prÃ©cÃ©dents, justifier qu'on peut se ramener Ã&nbsp; $P$ sans facteur carrÃ© et dont tous les facteurs irrÃ©ductibles partagent le mÃªme degrÃ© donnÃ© $d|n$.
		\item Montrer que pour tout $Q \in \F_p[X]$, 
		\[
		Q^{p^d}- Q = Q (Q^{(p^d-1)/2}-1) (Q^{(p^d-1)/2}+1)
		\] 
		et que $P |Q^{p^d}-Q$.
		\item En dÃ©duire que  
		\[
		P = \pgcd(P,Q) \pgcd(P,Q^{(p^d-1)/2}-1) \pgcd(P,Q^{(p^d-1)/2}+1).
		\]
		\item Avec l'aide du thÃ©orÃ¨me des restes chinois, montrer que si $P$ est rÃ©ductible, cette factorisation est non triviale pour au moins la moitiÃ© des $Q \in \F_p[X]$ de degrÃ© au plus $n-1$.
		\item En dÃ©duire l'algorithme probabiliste (de Cantor-Zassenhaus) pour factoriser $P$, et donner une estimation de son coÃ»t.
		\item Quel est son avantage par rapport Ã&nbsp; l'algorithme de Berlekamp ?
	\end{enumerate}
\end{exo}

\begin{exo}[Cantor-Zassenhaus pour les racines carrÃ©es]
	Ceci est une version simplifiÃ©e de l'exercice \ref{exo:algoCZ}, avec encore $p&gt;2$ (on peut le faire avant ou aprÃ¨s).
	
	Soit $P = X ^2 + a X + b \in \F_p[X]$.
	
	\begin{enumerate}
		\item Rappeler un algorithme utilisant le pgcd pour savoir si $P$ a deux racines ou non dans $\F_p$. On suppose pour la suite qu'on est bien dans ce cas, et on cherche Ã&nbsp; calculer les racines.
		
		\item Montrer qu'alors $P|X^p - X$ et identifier $A = \F_p[X]/(P)$.
		
		\item Montrer que pour tout polynÃ´me linÃ©aire $L(X) = m X + Y \in \F_p[X]$, $P|L^p -L$ (calculer dans $A$).
		
		\item En dÃ©duire que pour au moins $p^2/2$ polynÃ´mes linÃ©aires $L$, $1 \neq \pgcd(P,L^{(p-1)/2}-1) \neq P$.
		
		\item Donner un algorithme probabiliste pour calculer les racines de $P$ qui Ã©vite une recherche exhaustive. 
	\end{enumerate}
\end{exo}

\begin{exo}[Calcul de produit par FFT]
	Effectuer le produit de $X^2+2X-1$ et $2X+1$ par FFT dans $\F_5[X]$.
\end{exo}

\begin{exo}[GÃ©nÃ©ralisation Ã&nbsp; $\F_q$]
	
	Ici, $q$ est une puissance de $p$ et $\F_q$ un corps fini de caractÃ©ristique $p$.  Reprendre les Ã©noncÃ©s thÃ©oriques des exercices prÃ©cÃ©dents sur $\F_p[X]$ et les adapter Ã&nbsp; $\F_q[X]$.
\end{exo}

% Division euclidienne rapide\\
% \verb|https://xcas.univ-grenoble-alpes.fr/forum/viewtopic.php?f=39&amp;t=2497|

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

\iffalse {\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$.
\fi

\section{TP}

\begin{exo}
	V\'erifier/faire les parties calculatoires des exercices de TD.
\end{exo}

\begin{exo}[Algorithme de HÃ¶rner et facteurs de degrÃ© 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\Z$ pour $p$ premier.

\end{exo}

\begin{exo}[Test d'irrÃ©ductibilitÃ©]
	\begin{enumerate}
		\item[]
		\item \'Ecrire une fonction testant si un polyn\^ome est irr\'eductible
		modulo $p$. 
		\item L'utiliser pour Ã©crire un algorithme qui Ã&nbsp; $n$ et $p$ associe un polyn\^ome
		irr\'eductible unitiare de degr\'e $n$ dans $\F_p[X]$ puis une repr\'esentation
		du corps fini GF$(p,n)$.
	\end{enumerate}
\end{exo}

\begin{exo}[PolynÃ´mes et factorisation SQF]
	\begin{enumerate}
		\item[]
		\item \'Ecrire une fonction dÃ©terminant si un polynÃ´me est squarefree dans $\F_p[X]$.
		\item Prolongement : Ã©crire l'algorithme suggÃ©rÃ© dans l'exercice \ref{exo:factorSQF}  et le tester sur des exemples du TD.
	\end{enumerate}
	
	
\end{exo}

\begin{exo}[Exemple de factorisation DDF]
	\begin{enumerate}
		\item[]
		\item En se basant sur les idÃ©es de l'exercice \ref{exo:factorDDF} (pas besoin d'Ã©crire l'algorithme complet), d\'eterminer les degrÃ©s des facteurs irrÃ©ductibles de $X^7+X^5+2X^4+
		X^3+X^2+2X+1$ modulo 5
		et 7.
		\item  Quelle est la factorisation
		sur $\Q$ de ce polyn\^ome~?
		\item Plus gÃ©nÃ©ralement, Ã©crire l'algorithme de factorisation DDF et le tester sur cet exemple
	\end{enumerate}
\end{exo}

\begin{exo}[Corps $\F_{256}$ (\verb!GF(2,8)!)]
	Impl\'ementer le corps \`a 256 \'el\'ements de mani\`ere efficace
	(en utilisant un entier 8 bits et une table).
\end{exo}

\newpage 
\begin{exo}[FFT]
	\begin{enumerate}
		\item[]
		\item Trouver un nombre premier $p&lt;2^{31}$ de la forme $1+2^{25}k$, $k \in \Z$, on le fixe pour la suite.
		\item D\'eterminer une racine primitive $2^{25}$-i\`eme de l'unit\'e pour $p$.
		\item A quelle condition peut-on calculer le produit de deux polyn\^omes
		\`a coefficients dans $\Z/p\Z$ par FFT~?
		\item 
		Le faire sur un exemple en utilisant l'instruction \verb|fft| avec 3
		arguments.
		\item 
		Soit $n&lt;2^{31}$. Montrer qu'on peut effectuer un produit de polyn\^omes de $\Z/n\Z[X]$ dont la somme
		des degr\'es est $&lt;2^{25}$ en utilisant au plus 3 nombres premiers $p$ de ce type
		et 3 produits par FFT. 
		\item En d\'eduire une m\'ethode de multiplication de
		polyn\^omes \`a coefficients entiers par FFT.
	\end{enumerate}
\end{exo}



\end{document}</pre></body></html>