\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{ 1cm} TP12 Polyn{\^o}mes \hspace{1cm}}\hfill   agreg 2008 (F.Han\footnote{http://www.math.jussieu.fr/$\sim$han/agreg})}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
\columnsep 0.7cm
\begin{multicols}{2}
\exo
\qu Attention: \verb/rem(X^2+2*X+2,X^2+1);/  et \verb/rem(x^2+2*x+2,x^2+1);/
et \verb/rem([1,2,2],[1,0,1]);/
% restart;maple_mode(1);cas_setup(0,0,0,1,0,1e-10,10,[1,50,0,25],0,0,0); #radians,pas de cmplx, pas de  Sqrt
% rem(x^2+2*x+2,x^2+1);
% rem([1,2,2],[1,0,1]);
% rem(X^2+2*X+2,X^2+1); #X ne marche pas, il le fait en x. On pourra utiliser ,X
\exotitre{M{\'e}thode de Berlekamp}
% !s!<c>
%------------------------------Methode de Berlkamp-----------------------------
%!s!
\qu Cr{\'e}er une fonction \code{randP} qui donne un polyn{\^o}me unitaire au
hasard de degr{\'e}  $n$ {\`a} coefficients 
inferieurs {\`a} $20$. (On pourra {\'e}tudier si \code{sum} ou \code{add} est
appropri{\'e}e, ou si l'on pr{\'e}f{\`e}re utiliser le point de vue d'xcas, ie polyn{\^o}me
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{\`e}re le polyn{\^o}me $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
\qu V{\'e}rifier 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{\`e}re un nombre premier $p$.
\squ Cr{\'e}er une proc{\'e}dure \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"); [[0]] fi;
% end;
%!s!
\qu Tester pour diff{\'e}rentes 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{\'e}f{\'e}rence\footnote{On le prend petit
  pour {\'e}ventuellement illustrer la remont{\'e}e 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{\'e}ment le nombre de facteurs dans $\rela[X]$?
%!s!<c>
% Non, il peut y avoir moins de facteurs dans Z.
%!s!
% p:=23; Gcd(P,diff(P,x)) mod p;
\qu Prendre un {\'e}l{\'e}ment $Q$ du noyau de $F$. V{\'e}rifier 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{\'e}dure \code{unfacteur} qui pour un diviseur $d$ de $P$
trouve un facteur non trivial de $d$ par la  m{\'e}thode pr{\'e}c{\'e}dente. 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{\'e}dure \code{facteurpseudoirred} qui utilise par
r{\'e}currence \code{unfacteur} pour trouver un facteur probablement
irr{\'e}ductible de $P$. Cr{\'e}er un test pour savoir si un polyn{\^o}me sans
facteurs multiples est irr{\'e}ductible. 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{\'e}thode. Que peut on faire pour v{\'e}rifier si tout ces facteurs sont irr{\'e}ductibles?
%!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!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotitre{Factorisation sans carr{\'e}s}
%!s!<c>
%---------------------------------------------------------------
%!s!
\qu
On consid{\`e}re des {\'e}l{\'e}ments de $\rela/3\rela[x]$  $a,b,c,d,e$ premiers entre eux
deux {\`a} deux, et sans facteurs multiples. On note $P=a.b^2.c^3.d^4.e^6$, et
$Q=a.b.d$.  
\squ Que repr{\'e}sente $Q$ en fonction de $P$ et $P'$ dans $\rela/3\rela[x]$?
\squ Illustrer en utilisant des variables formelles $a,b,c,d,e$ comment obtenir
$a,b,d$ en ne connaissant que $P$ et $Q$
%purge(a,b,c,d,e);
% P:=a*b^2*c^3*d^4*e^6;
%Q:=a*b*d; #Q est P divise par le pgcd de P et P'
%T1:=P;V1:=Q;
%V2:=gcd(T1,V1);T2:=normal(T1/V2);
%V3:=gcd(T2,V2);T3:=normal(T2/V3);normal(V2/V3); #on obtient a
%V4:=gcd(T3,V3);T4:=normal(T3/V4);normal(V3/V4); #on obtient b
%V5:=gcd(T4,V4);T5:=normal(T4/V5);normal(V4/V5); #on obtient d
\squ Expliquer ensuite comment obtenir le polyn{\^o}me $c.e^2$, puis
comment en d{\'e}duire $c$ et $e$.
% !s!<c>
%On a obtenu le polynome T5=c^3e^6. Ce polynome en n'est autre que
%Q(x^3) ou Q=c.e^2. On recommence alors avec Q. (On obtient  c.e
%en divisant Q par le pgcd de Q et Q').
%!s!
%T6:=c*e^2;V6:=c*e;
%V7:=gcd(T6,V6);T7:=normal(T6/V7);
%V8:=gcd(T7,V7);T8:=normal(T7/V8);normal(V7/V8); #on obtient c
%V9:=gcd(T8,V8);normal(V8/V9); #on obtient e
\qusqu Cr{\'e}er une proc{\'e}dure \code{facto1(P,p)} donnant pour chaque $i$ premier avec la
caract{\'e}ristique $p$ le produit des facteurs irr{\'e}ductibles de
multiplicit{\'e} $i$ dans $P$.
%!s!<p>
%facto1:=proc(P,p)
%local VV,T,V,k,L;
%T:=Gcd(P,diff(P,x)) mod p;
%V:=Quo(P,T) mod p; #Attention, il faut faire les divisions modp
%V:=Gcd(P,V) mod p;T:=Quo(P,V) mod p; 
%L:=[];
%k:=1;
%while degree(V) > 0 do
%VV:=V;V:=Gcd(T,V) mod p; T:=Quo(T,V) mod p;
%if degree(V)<degree(VV) then L:=[op(L),[Quo(VV,V) mod p,k]]; fi;
%k:=k+1;
%od;
%L;
%end;
%!s!
\squ Trouver un bon polyn{\^o}me pour tester \code{facto1}. (Par exemple 6
multiplicit{\'e}s diff{\'e}rentes, dont deux multiples de $p$, les facteurs multiples
n'{\'e}tant pas tous irr{\'e}ductibles.)
% Factor(x^49-x) mod 7; #On cherche des facteurs irred de degre 2 distincts pour connaitre la reponse.
% P:=normal((x+1)*(x^2-2*x+1)^2*(x+2)^3*(x^2+3*x-2)^3*x^7*(x^2-x-3)^7*(x^2-x-1)^9*(x^2-2*x-2)^14) mod 7;
% Factor(P) mod 7; #On verifie que nos facteurs sont bien premiers entre eux.
%facto1(P,7);
\qu Cr{\'e}er \code{facto2} en modifiant la proc{\'e}dure pr{\'e}cedente pour
obtenir aussi ceux de multplicit{\'e} multiple de $p$. 
%!s!<p>
%facto2:=proc(P,p)
%local VV,T,V,k,L,j;
%T:=Gcd(P,diff(P,x)) mod p;
%V:=Quo(P,T) mod p; #Attention, il faut faire les divisions modp
%T:=Quo(P,V) mod p; 
%L:=[];
%k:=1;j:=1
%while degree(T)>0 do
%while degree(V) > 0 do
%VV:=V;V:=Gcd(T,V) mod p; T:=Quo(T,V) mod p;
%if degree(V)<degree(VV) then L:=[op(L),[Quo(VV,V) mod p,k]]; fi;
%k:=k+j;
%od;
%//Attention pour poly2symb les coeffs sont dans l'ordre des degres decroissants
%j:=j*p;k:=j;T:=poly2symb([seq(coeff(T,i*p),i=degree(T)/p..1)],x);
%V:=Quo(T,Gcd(T,diff(T,x)) mod p) mod p;
%T:=Quo(T,V) mod p;
%od;
%L;
%end;
%!s!
%facto2(P,7);
\newpage
\end{multicols}

\end{document}

