\documentclass[12pt,a4paper]{article}
\usepackage{multicol}
\usepackage[french]{babel}
\newfont{\mini}{cmssi10 scaled 480}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\euro{\mbox{\textsf{C}\kern -2.33em{\raise0.24ex\vbox{\small\it =}}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\fin{\nolinebreak \raise-0.1em\hbox{$\Box$}}
\def\stackunder#1#2{\mathrel{\mathop{#2}\limits_{#1}}}
\def\dual{ ^{\rm v}}
\def\bidual{ ^{\rm vv}}
\def\primedual{ ^{\prime \rm v}}
\def\ideal{{\cal J}}
\def\LL{{\cal L}}
\def\max{{\cal M}}
\def\quot#1#2{\mbox{\raise 0.1cm\hbox{$#1$}{\big /}\raise -0.1cm\hbox{$#2$}}}
\def\danger{{\Large \bf
    $\bigtriangleup$}\kern-0.32cm\raise0.05cm\hbox{\small
    !}\kern0.32cm\lower0.05cm\hbox{}}
%%%%%%%
\newlength{\largeurtmp}
\def\rela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.6\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.6\largeurtmp}
\def\petitrela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.4\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.4\largeurtmp}
\def\petitcomplex{{
    \settoheight{\largeurtmp}{$_C$}{\rm C}\kern -\largeurtmp
    \rule{0.25pt}{1.3\largeurtmp}\kern \largeurtmp}}
\def\complex{{
    \settoheight{\largeurtmp}{Q}{\rm C}\kern -0.66\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.66\largeurtmp}}
\def\ratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.75\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.75\largeurtmp}}
\def\petitratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.6\largeurtmp
    \rule{0.25pt}{0.6\largeurtmp}\kern 0.6\largeurtmp}}
\newcommand{\proj}{{\rm I} \! {\rm P}}
\newcommand{\reel}{{\rm I} \! {\rm R}}
\newcommand{\Fp}{{\rm I} \! {\rm F}_p}
\newcommand{\nat}{{\rm I} \! {\rm N}}
%%%%%%%%%%%%%%%Debut de macros de fiches d'exos
%%les macros sont \exo, \qu, \quskip \squ \qusqu \qusquskip
\newcounter{exo}
\newcounter{question}
\newlength{\lng}
\newcounter{sousquestion}
\setcounter{exo}{1}
\def\exo{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}:}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\exotitre#1{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}: #1}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\qu{

  \addtocounter{question}{1}\arabic{question})
  \setcounter{sousquestion}{1} }
\def\quskip{

  \bigskip
  \qu}
\def\squ{

  \settowidth{\lng}{\arabic{question})
  }\hspace{\the\lng}\alph{sousquestion}) \addtocounter{sousquestion}{1}} 
\def\qusqu{\qu\nopagebreak \vskip -1\baselineskip \squ}
\def\qusquskip{\quskip\nopagebreak \vskip -1\baselineskip \squ}

%%reference pour exos,squ \`a placer avant la question, qu est a placer apres
\def\labelexo#1{\expandafter\edef\csname refexo#1\endcsname {\Roman{exo}}}
\def\refexo#1{\csname refexo#1\endcsname}
\def\labelqu#1{\expandafter\edef\csname refqu#1\endcsname {\arabic{question})}}
\def\refqu#1{\csname refqu#1\endcsname}
\def\labelsqu#1{\expandafter\edef\csname refsqu#1\endcsname
  {\arabic{question}\alph{sousquestion})}} 
\def\refsqu#1{\csname refsqu#1\endcsname}  

%%%%%%%%%%fin de macros fiche d'exos
%%macros taille page
\newlength{\elargir}
\setlength{\elargir}{2.5cm}
\addtolength{\leftmargin}{-\elargir}
%%\addtolength{\hoffset}{-\elargir}
\addtolength{\oddsidemargin}{-\elargir}
\addtolength{\evensidemargin}{-\elargir}
\addtolength{\elargir}{\elargir}
\addtolength{\textwidth}{\elargir}
\addtolength{\textheight}{13\baselineskip}
\topmargin=-5\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\everymath={\displaystyle}
\begin{document}
\noindent{\bf Universit\'e de Paris 7 \hfill \framebox{\Large \bf
    \hspace{ 0.2cm}TP15 Factorisation des Polyn\^omes \hspace{0.2cm}}\hfill   agreg 2012 (F.Han\footnote{http://www.math.jussieu.fr/$\sim$han/agreg})}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
\columnsep 0.7cm
%%\begin{multicols}{2}
% restart;maple_mode(0);cas_setup(0,0,0,1,0,1e-10,10,[1,50,0,25],0,0,0); //radians,pas de cmplx, pas de  Sqrt
%!s!<c>
%----------------------Initiation syntaxe modulaire et puissance rapide---------------------
%!s!
\exo
\qu Essayez le programme suivant (en mode xcas): \verb/f:=proc(P) P:=P%0;end;/
Que fait: \verb/Q:=x+1%5;f(Q);Q/
% !s!<c>
% On peut modifier l'argument passe a une fonction, a l'interieur de la
% fonction, en revanche, une fois sorti de la fonction sa valeur initiale avant
% l'appel est restitu\'ee. Par exemple la fonction suivante remonte P dans Z (ie
% passer modulo 0)
% !s!
% f:=proc(P) P:=P%0;end;
% Q:=x+1%5;f(Q);Q
\qusqu On pose \verb/a:=27%101;/. Comment est calcul\'e \verb/a^j/ par xcas lorsque j
est grand? Faites afficher les temps de calculs pour $j=2^{2^i}$ avec
$i\in\{3,4,5,6,7,8,\dots,18\}$. Commentez.
% a:=27%101;
% l:=[seq([2^j,time(a^(2^(2^j)))[0]],j=3..18)]:;l:=[op(l),seq([2^(j/7),time(a^(2^(2^j)))[0]],j=7*14..16*7)]:;
\squ Illustrez graphiquement la croissance en $O(\ln j)$. Afficher des gros
points et une droite de r\'egression lin\'eaire bleue.
% d1:=scatterplot(l):; // la croissance lineaire.
% d2:=line(y-[linear_regression(l)]*[x,1]):;// mal adapte a la repartition irreguliere des abscisses de l
% affichage(d1,point_width_2),affichage(d2,bleu);
\qu On consid\`ere le polyn\^ome: \linebreak\verb/P:=2*(x^4+x^3+x^2+x+1);/ et le polyn\^ome
\verb/Q:=P % 7/
% P:=2*(x^4+x^3+x^2+x+1);
% Q:= P % 7;
\squ Quel est le reste de $x^7$ par $Q$? (ie en travaillant dans
$\rela/7\rela[x]$).
%rem(x^7,Q);// la division est bien faite dans Z/7Z
\squ Que donne \verb/rem(x^(2^10),Q);/ et \verb/rem(x^(2^33),Q)/?
%rem(x^(2^10),Q);//Attention, ca a l'air long, signe que la puissance n'est pasrapide
%rem(x^(2^33),Q);//n'est plus evalue. trop gros
\squ Comment calculer la puisance rapide de $x$  dans $\rela/p\rela[x]/(P)$? Par
exemple calculer: $(1+x)^{2^{33}} [P]$ dans $\rela/7\rela[x]$. (A retenir)
%!s!<c>
% Pour faire des puissances rapides de polyn\^omes a coefficients dans Z/pZ modulo
% un autre polynome on le fait avec l'intruction powmod qui attend des polynomes
% a coefficients entiers, et le nombre premier.  Cf ?powmod
%!s!
%powmod((1+x),2^33,101,P,x);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotitre{M\'ethode de Berlekamp}
%!s!<c>
%------------------------------Methode de Berlekamp-----------------------------
%!s!
\qu Cr\'eer une fonction \code{randP} qui donne un polyn\^ome unitaire au
hasard de degr\'e  $n$ \`a coefficients 
inferieurs \`a $20$. (On pourra \'etudier si \code{sum} ou \code{add} est
appropri\'ee, ou si l'on pr\'ef\`ere utiliser le point de vue d'xcas, ie polyn\^ome
donn\'e par la liste de ses coefficients).
% sum(rand(20)*x^j,j=0..n);  //sum,mul,add evaluent le random avant!
% randP:=n->poly2symb([1,seq(rand(20),j=0..n-1)],x);
\qu On consid\`ere le polyn\^ome $P$ obtenu par \code{expand(mul([seq(randP(rand(7)),i=1..5)]));}
% P:=expand(mul([seq(randP(rand(7)),j=1..5)])); //on met un seq pour avoir des rand differents
%P:=x^16+x^14+58*x^15+1386*x^14+17715*x^13+131260*x^12+578697*x^11+1538013*x^10+2648041*x^9+3687447*x^8+4993299*x^7+5858116*x^6+5979221*x^5+5239798*x^4+4098561*x^3+3176188*x^2+1660466*x+705432;
\qu V\'erifier que $P$ n'a que des racines simples, sinon recommencer.
% gcd(P,diff(P,x)); //Pour berlekamp, il ne faut pas de facteurs multiples.
\qu On consid\`ere un nombre premier $p$.
\squ Cr\'eer une proc\'edure \code{berl(p,P)} qui 
calcule la matrice \code{F} de l'application $\rela/p\rela[X]/(P) \to
\rela/p\rela[X]/(P)$ $f \mapsto f^p-f$ dans la base
$(X^i)_{0,\dots,\deg P-1}$, et retourne son noyau. ( On s'arrangera pour que le
calcul des puissances soit rapide). Am\'eliorez cette fonction pour
qu'elle ne fasse cela que si $P$ n'a pas de facteurs multiples dans
$\rela/p\rela[x]$. Retourner \verb/[[0]]/ dans ce cas.
% !s!<c>
% Attention \`a la bonne instruction pour trouver un noyau mod p. en mode maple
% Prendre la forme  inerte: Nullspace. De plus, il faut aussi faire attention pour les
% coefficients des polynomes, on les veut tous jusque degree(P)-1 meme si leur
% degr\'e est plus petit.
%!s!
%!s!<p>
% berl:=proc(p,PP)
% local f,L,F,n;
% PP:=PP % p; // pour le calcul de pgcd on s'assure/(on force) que P est modulo p
% if degree(gcd(PP,diff(PP,x))) =0 then
% n:=degree(PP)-1;
% f:=(i0,j0)->coeff(powmod(x,i0*p,p,PP % 0,x),x,j0);
% L:=matrix(n,n,f)-idn(n);
% F:=transpose(L) % p;
% ker(F);
% else print("facteurs multiples",p); [[0]] fi;
% end;
%!s!
\qu Tester pour diff\'erentes valeurs de $p$ le rang de $F$. Illustrer le lien
entre la dimension du noyau de $F$, et la factorisation de $P$ sans $\rela/p\rela$
%!s!<m>
% p:=1:;L:=[];for i0 from 1 to 10 do
% p:=nextprime(p):; L:=[op(L),[rowdim(berl(p,P)),p,factor(P % p) ]] od:;
% !s!
% L;
\qu Comprendre le th\'eor\`eme de Berlekamp\footnote{Cf par exemple Demazure cours
  d'alg\`ebre, ou Cohen: a course in computational number theory}:

{\it Soit $P$ un \'el\'ement de $F_q[x]$ sans
facteurs multiples. Alors le nombre de facteurs irr\'eductibles de $P$ est la
dimension du noyau de l'application $F_q$-lin\'eaire:
$$
\begin{array}{lll}
  F_q[x]/(P) & \to & F_q[x]/(P) \\
  f & \mapsto & f^q-f
\end{array}
$$
}
\qu Choisir un nombre premier impair de pr\'ef\'erence\footnote{On le prend petit
  pour \'eventuellement illustrer la remont\'ee Henselienne ensuite.} plus petit
que 20 o\`u le nombre de facteurs est assez petit, et tel que   $P$ ait peu de
facteurs dans $\rela/p\rela$, et  soit  sans facteurs
multiples dans $\rela/p\rela[x]$  pour cette valeur de $p$. Le
nombre de facteurs est il forc\'ement le nombre de facteurs dans $\rela[X]$?
%!s!<c>
% Non, il peut y avoir moins de facteurs dans Z.
%!s!
% p:=7; P:=P % p ;gcd(P ,diff(P ,x)) ;
\qu Prendre un \'el\'ement $Q$ du noyau de $F$. V\'erifier qu'il convient.
\squ Si $P_i$ est un facteur irr\'eductible de $P$ dans $\rela/p\rela[x]$,
rappelez quelles sont les valeurs possibles pour $Q^{\frac{p-1}{2}} [P_i]$. Que
repr\'esente la condition   $Q^{\frac{p-1}{2}} =1[P]$? Pensez vous qu'elle se
r\'ealise souvent?
% !s!<c>
% Comme Q est dans le noyau, on a  Q^(p-1)=1[Pi] pour tout facteur irred Pi
% de P.
% De plus Q^((p-1)/2)=1 modulo Pi ssi Q est un carre
% dans le corps Fp[x]/Pi. Ce qui represente a peu pres une chance sur 2. Pour
% avoir Q^((p-1)/2)=1  modulo P il faudrait que pour tout i Q soit un carre
% dans Zp[x]/(Pi). (idem avec -1). On a donc bien plus de chance d'avoir des i
% ou Q est un carre et d'autres ou il ne l'est pas. Dans cette situatino tres
% probable, le pgcd de Q^((p-1)/2) -1 et de P n'est donc ni 1 ni P, puisque
% c'est le produit des Pi tels que $Q$ soit un carre dans Zp[x]/(Pi).
%!s!
\squ Trouver un facteur non trivial de $P$.
%N:=berl(p,P);LX:=[seq(x^(j-1),j=1..degree(P))];
%Q:=(LX*N[2]);
%rem(powmod(Q % 0 ,p,p,P % 0,x)-Q,P ); //  verification:
%gcd(Q ,P);  //l'un des 3 pgcd est non trivial:
%A:=rem(powmod(Q % 0,(p-1)/2,p,P % 0,x)-1,P ) ;
%gcd(A,P);
%B:=rem(powmod(Q % 0,(p-1)/2,p,P % 0,x)+1,P);
%gcd(B,P);
\qu Faire une proc\'edure \code{unfacteur} qui pour un diviseur $d$ de $P$
trouve un facteur non trivial de $d$ par la  m\'ethode pr\'ec\'edente. Si au
bout de quelques essais\footnote{Par exemple 3, inutile de faire une boucle} ce facteur est toujours $d$, elle retourne alors $d$.
%!s!<m>
% unfacteur:=proc(d)
% i0:=1;
% A:=1;B:=1;rep:=1;
% r:=[seq(rand(p),i0=1..rowdim(N))]*N; //un element du noyau au hasard
% Q:=(LX*r);
% //On fait 3 essais;
% A:=gcd(Q,d);
% if degree(A)*(degree(A)-degree(d))<>0 then rep:=A ;
% else A:=rem(powmod(Q % 0 ,(p-1)/2,p,P % 0,x)-1,P);
% A:=gcd(A,d);
% if degree(A)*(degree(A)-degree(d))<>0 then rep:=A ;
% else A:=rem(powmod(Q % 0,(p-1)/2,p,P % 0,x)+1,P);
% A:=gcd(A,d);
% if degree(A)*(degree(A)-degree(d))<>0 then rep:=A fi;
% fi;
% fi;
% if degree(rep)=0 then d else rep  fi;
% end proc;
%!s!
% unfacteur(P);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\qu Faire une proc\'edure \code{facteurpseudoirred} qui utilise par
r\'ecurrence \code{unfacteur} pour trouver un facteur probablement
irr\'eductible de $P$. Cr\'eer un test pour savoir si un polyn\^ome sans
facteurs multiples est irr\'eductible. Tester le facteur obtenu.
%!s!<m>
% facteurpseudoirred:=proc(d)
% t:=unfacteur(d);
% tt:=d;
% while (degree(t)<degree(tt)){tt:=t;t:=unfacteur(t);};
% t;
% end;
%!s!
% f:=facteurpseudoirred(P);
% !s!<c>
% Si le noyau est de dim 1, f est irreductible.
%!s!
% if (rowdim(berl(p,f))==1) then print ("f est irred") fi;
\qu Tentez de factoriser $P$ dans $\rela/p\rela[X]$ par cette
m\'ethode. Que peut on faire pour v\'erifier si tout ces facteurs sont irr\'eductibles?
% !s!<c>
% La construction dans la boucle suivante cree une liste L qui commence
% systematiquement par 1, les  facteurs de P trouves sont ranges dans L apres.
%!s!
%!s!<m>
% T:=P;a:=1;L:=[];
%while(degree(T)>0){T:=quo(T,a);L:=[op(L),a];a:=facteurpseudoirred(T)}:;L;
%!s!
%!s!<c>
%Le nombre de facteurs doit etre la dim de ker F, on teste si l'on a
%trouve tous les facteurs ainsi:
%!s!
% if nops(N)==(nops(L)-1) then print("on a bien trouve tous les facteurs") fi;
%!s!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%\newpage
%%\end{multicols}

\end{document}

