\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}TP14 Factorisation des Polyn\^omes 2\hspace{0.2cm}}\hfill   agreg 2010 (F.Han\footnote{http://www.math.jussieu.fr/$\sim$han/agreg})}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
\columnsep 0.7cm
\begin{multicols}{2}
\exotitre{M\'ethode de Berlekamp}
% !s!<c>
%------------------------------Methode de Berlkamp-----------------------------
%!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^i,i=0..n);  #sum,mul,add evaluent le random avant!
% randP:=n->poly2symb([1,seq(rand(20),i=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)),i=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.
% !s!<c>
% Attention \`a la bonne instruction pour trouver un noyau mod p. 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!<m>
% berl:=proc(p,PP)
% local L,tmp,i,j,F;
% L:=[];
% if degree(Gcd(PP,diff(PP,x)) mod p) =0 then
% for i from 0 to degree(PP) - 1 do
% tmp:=powmod(x,i*p,p,PP,x); #On utilise la puissance rapide 
% tmp:=Rem(tmp-x^i,PP) mod p;
% l:=[seq(coeff(tmp,x,j),j=0..degree(PP)-1)];
% L:=[op(L),l];
% od:
% F:=transpose(L);Nullspace(F) mod p;
% 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 i from 1 to 10 do
% p:=nextprime(p):L:=[op(L),[rowdim(berl(p,P)),p,Factor(P) mod p]] od;
%!s!
\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; Gcd(P,diff(P,x)) mod p;
\qu Prendre un \'el\'ement $Q$ du noyau de $F$. V\'erifier qu'il convient,
et 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,p,p,P,x)-Q,P) mod p; #  verification:
%Gcd(Q,P) mod p;  #l'un des 3 pgcd est non trivial:
%A:=Rem(powmod(Q,(p-1)/2,p,P,x)-1,P) mod p;
%Gcd(A,P) mod p;
%B:=Rem(powmod(Q,(p-1)/2,p,P,x)+1,P) mod p;
%Gcd(B,P) mod 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)
% i:=1;
% A:=1;B:=1;rep:=1;
% r:=[seq(rand(p),i=1..rowdim(N))]*N; #un element du noyau au hasard
% Q:=(LX*r);
% #On fait 3 essais;
% A:=Gcd(Q,d) mod p;
% if degree(A)*(degree(A)-degree(d))<>0 then rep:=A ;
% else A:=Rem(powmod(Q,(p-1)/2,p,P,x)-1,P) mod p;
% A:=Gcd(A,d) mod p;
% if degree(A)*(degree(A)-degree(d))<>0 then rep:=A ;
% else A:=Rem(Powmod(Q,(p-1)/2,p,P,x)+1,P) mod p;
% A:=Gcd(A,d) mod p;
% 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)) do tt:=t;t:=unfacteur(t); od;
% 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!<m>
% T:=P;a:=1;L:=[];
%while degree(T)>0 do T:=Quo(T,a) mod p;L:=[op(L),a];a:=facteurpseudoirred(T); od: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!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\`u
%!s!<c>
%----------------------------Exo remontee Henselienne--------------------------
%!s!
\exotitre{Remont\'ee Henselienne}
On peut prendre le polyn\^ome $P$ pr\'ec\'edent
ou un autre.
\qu Prendre un diviseur $A$ de $P$ dans $\rela/p\rela[X]$. On note $B=P/A$
dans $\rela/p\rela[X]$. Trouver $U,V$ tels que $A.U+B.V=1 [p]$
%p:=7;
% 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;
%L:=op(Factor(P) mod 7);
% A:=x^2+2*x+3;B:=Quo(P,A,x) mod p; [U,V,DD]:=Gcdex(A,B,x) mod p;
%invDD:=igcdex(DD,p)[1];U:=U*invDD;V:=V*invDD;
% Rem(A*U+B*V,P,x) mod p; # verification:
%!s!<c>
% (A+p^iA')(B+p^iB')=P[p^(i+1)];A'B+B'A=(P-A.B)/p^i;A'=V*(P-AB)/p^i[p];
%!s!
\qu Obtenir un diviseur de $P$ dans $\rela/p^2\rela[X]$ congru \`a $A$
modulo $p$. Puis illustrer une remont\'ee aboutissant \`a un facteur de $P$ dans
$\rela[x]$. 
%!s!<c>
% On veut AU+BV=1[P];AB=P[p^i];(A+p^iAA)(B+p^iBB)=P[p^(i+1)]
%!s!
%!s!<m>
% for i from 1 to 4 do
% PP:=normal((P-A*B)/p^i);AA:=Rem(PP*V,A,x) mod p;
% BB:=Quo(normal(PP-B*AA),A,x) mod p;
% A:=normal(A+p^i*AA);B:=normal(B+p^i*BB);
% A;
% od;
% !s!
% !s!<c>
% La remontee se stabilise, le facteur peut convenir, on teste s'il divise dans Z
%!s!
% if rem(P,A,X)=0 then print(A,"est un diviseur dans Z") fi;
\qu Illuster que certaines remont\'ees de donnent pas un facteur dans $\rela[x]$
%!s!<c>
% Mais, il ne convient pas forcement on a eu de la chance, il faudrait alors
% essayer d'autres facteurs, 
%  ou bien des produits. Si la factorisation modulo $p$ a trop de
% facteurs c'est plus long. DAns l'exemple suivant, ca ne se stabilise pas, ce
% facteur  modulo p ne vient pas d'un facteur dans Z
% !s!
% A:=x-2;B:=Quo(P,A,x) mod p; [U,V,DD]:=Gcdex(A,B,x) mod p;
%invDD:=igcdex(DD,p)[1];U:=U*invDD;V:=V*invDD;
% Rem(A*U+B*V,P,x) mod p; # verification:
%!s!<m>
% for i from 1 to 10 do
% PP:=normal((P-A*B)/p^i);AA:=Rem(PP*V,A,x) mod p;
% BB:=Quo(normal(PP-B*AA),A,x) mod p;
% A:=normal(A+p^i*AA);B:=normal(B+p^i*BB);
% A;
%od;
%!s!
\qu Quel est $max_i C^i_m$? Faire une proc\'edure de $m,P$: \code{borne}
qui calcule une valeur flottante de ce nombre multipli\'e par la norme
de $P=\sum_i a_i.x^i$: $\sqrt{\sum_i   |a_i|^2}$.
%!s!<m>
% borne:=proc(m,P)
%A:=matrix([coeffs(P)]);
%binomial(m,floor(m/2))*evalf(sqrt((A*transpose(A))[1,1]),5);
%end;
%!s!
%borne(5,P),evalf(p^10,3);#Donc 10 iterations suffisent.


\newpage
\end{multicols}

\end{document}

