\documentclass{article}
\usepackage[francais]{babel}
%\usepackage[OT1]{fontenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{xspace}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}

\begin{document}
\begin{center}
{\Large TP factorisation}
\end{center}

{\bf Exercices~:}
\begin{enumerate}
\item Déterminer le nombre de racines de $-x^7+x^4+12x-5$ comprises
entre 0 et 6 (en utilisant les suites de Sturm, on donnera les
d\'etails des calculs).
\item \'Ecrire un programme calculant la suite de Sturm d'un polynôme
supposé squarefree (on peut tester avec \verb|sqrfree|), en utilisant
l'algorithme d'Euclide.
\item Trouver les facteurs de degré 1 s'ils existent de
$3x^5+25x^4+67x^3+77x^2+55x+13$ en remontant ses racines
dans $\Z/pZ[X]$ pour $p$ premier bien choisi.
\item Factoriser le polynôme $x^5+x+1$ par la méthode 
de Berlekamp.
\item Calculer avec un logiciel les valeurs numériques des racines
complexes de $P(x)=x^5+x+1$. Trouver les combinaisons de racines
dont la somme est entière (aux arrondis près). En déduire la factorisation
en facteurs irréductibles sur $\Z$ de $P$.
\item Factorisation numérique sur $\C$. \'Ecrire un programme
qui calcule une racine d'un polynôme à coefficients complexes
en utilisant une méthode itérative de type méthode de Newton 
(avec éventuellement un préfacteur lorsqu'on débute la recherche).
Les polynômes seront représentés par la liste de leurs coefficients
et l'évaluation faite par la méthode de Horner.
Trouver ensuite toutes les racines du polynôme en éliminant la
racine trouvée (toujours avec Horner). Trouver les combinaisons
de racines correspondant à un facteur à coefficients entiers.
\item Même question pour les facteurs de degré 2 d'un polynôme à coefficients
réels sans racines réelles en utilisant la méthode de Bairstow décrite
ci-dessous.\\
On cherche un facteur $F=x^2+sx+p$ de $P$, on calcule le quotient et le reste
de la division $P=FQ+R$ par une méthode de type Horner, il s'agit de 
rendre $R$ (vu comme un vecteur à 2 composantes) nul. On calcule
donc $\partial_{s,p} R$ (en cherchant le quotient et le reste
de $xQ$ et $Q$ par $F$, pourquoi?) et on pose~:
\[(s,p)_{n+1}=(s,p)_n- \lambda (\partial_{s,p} R)^{-1} R (s,p)_n\]
où $\lambda$ est un préfacteur compris entre 0 et 1 et ajusté à 1 
lorsqu'on est proche du facteur.
\item Soit $p$ un entier premier et $P$ un polynôme \`a
coefficients dans $\Z/p\Z$. On a la relation
\[ gcd(X^{p^k}-X,P) = \prod_{ f | P, \mbox{\small deg}(f) | k} f, 
\quad f \mbox{ irréductible} \]
En utilisant cette relation, 
déterminer les degrés des facteurs de 
\[ (x^3+x+1)(x^4+x+1) \]
modulo 5 et 7 (sans utiliser la commande factor). 
Peut-on en déduire que $x^3+x+1$ et
$x^4+x+1$ sont irréductibles sur $\Z$?
\item Utiliser les options ``verbose'' de votre logiciel de calcul formel
pour factoriser $x^{202}+x^{101}+1$ et vérifiez que vous avez compris
la méthode utilisée.
\item Montrer que $2x+x^2y+x^3+2x^4+y^3+x^5$ est irréductible sur $\Z$
sans utiliser l'instruction factor à 2 variables (on pourra factoriser 
pour quelques valeurs de $x$ ou de $y$)

\end{enumerate}

\end{document}