\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 \hspace{1cm}}\hfill   agreg 2007 (F.Han)}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
\columnsep 0.7cm
\begin{multicols}{2}
% interface(screenwidth=120);
%with(LinearAlgebra):
\exo
\qu Trouver le reste de $X^{100000}$ par $P$ dans
$\rela/101\rela[X]$. (On comparera les vitesses avec \code{Rem() mod}
et \code{Powmod() mod})
%# Rem plus lent que Powmod 
% Rem(X^100000,P,X) mod 101;
%Powmod(X,100000,P,X) mod 101;
\qu Comment trouver la suite des coefficients du polyn{\^o}me
$X^4+2X+1$? Comment cr{\'e}er une suite de longueur  $\deg P$ 
dont le i{\`e}me terme soit le coefficient de $X^i$ dans le polyn{\^o}me
pr{\'e}c{\'e}dent.
% #Attention,  coeffs n'affiche pas  les coefficicients nuls
% l:=[coeffs(X^4+2*X+1)];
% op(l),seq(0,i=1..degree(P)-nops([l]));
% # donc la methode precedente perd les zeros intermediaires. 
% # Il faut donc faire ainsi: 
% l:=[seq(coeff(X^4+2*X+1,X,i),i=0..degree(P)-1)];
\qu Comment en partant de la liste vide
\code{L:=[];} rajouter succ{\'e}ssivement les {\'e}l{\'e}ments $1$ puis $2$ puis
$4$ {\`a} $L$.
% L:=[]; L:=[op(L),1];L:=[op(L),2];L:=[op(L),4];
%%%%%%%%%%%%%%%%%%%%%%
\exotitre{Factorisation dans $\rela/p\rela[X]$}
\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 laquelle des instructions
\code{sum} et \code{add} est la plus appropri{\'e}e).
% #sum evalue le random avant!
% sum(rand(0..20)()*X^i,i=0..n);
% randP:=n->add(rand(0..20)()*X^i,i=0..n-1)+X^n;
\qu On consid{\`e}re le polyn{\^o}me $P$ obtenu par \code{P:=expand(mul(randP(rand(1..7)()),i=1..5));}
% P:=expand(mul(randP(rand(1..7)()),i=1..5));
\qu V{\'e}rifier que $P$ n'a que des racines simples, sinon recommencer.
% #Pour berlekamp, il ne faut pas de facteurs multiples.
% gcd(P,diff(P,X));
\qu On consid{\`e}re le nombre premier $p$.
\squ Cr{\'e}er une proc{\'e}dure \code{berl} qui {\`a} un  nombre premier $p$
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.
% #Attention {\`a} la bonne instruction pour trouver un noyau mod p, il y
% #a 3 fonctions: nullspace de linalg, NullSpace de LinearAlgebra et
% # enfin Nullspace qui ne depend d'aucun packages. c'est Nullspace
% #qui marche bien mod p.
% berl:=proc(p)
% L:=[];
% for i from 0 to degree(P) - 1 do
%% l:=[seq(coeff(Rem(X^(i*p)-X^i,P,X) mod p,X,j),j=0..degree(P)-1)];
% L:=[op(L),Vector(l)];
% od:
% F:=Matrix(L);Nullspace(F) mod p;
% end proc;
\qu Tester pour diff{\'e}rentes valeurs de $p$ le rang de $F$. Que
repr{\'e}sente la dimension du noyau de $F$?
% p:=2:L:=[];for i from 1 to 10 do ; p:=nextprime(p+1):L:=[op(L),Vector([nops(berl(nextprime(p))),p])];od:L;
\qu Choisir un nombre premier impair o{\`u} le nombre de facteurs est le plus
petit apparu. V{\'e}rifier que $P$ est sans facteurs multiples dans
$\rela/p\rela[X]$ pour le $p$ choisi, sinon prenez en un autre. Ce
nombre est il forc{\'e}ment le nombre de facteurs dans $\rela[X]$?
% #Non
% #NB: lorsque l'on redemarre maple, parfois on a l'air d'avoir toujours le meme P
% # pour qu'il y ait un peu de remontee, on prend un p<20
% p:=17; 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);LX:=Matrix(1,degree(P),(i,j)->X^(j-1));
%Q:=(LX.N[1])[1];
%#  verification:
%Rem(Powmod(Q,p,P,X)-Q mod p,P,X) mod p;
%# l'un des 3 pgcd est non trivial:
%Gcd(Q,P) mod p;
%A:=Rem(Powmod(Q,(p-1)/2,P,X)-1 mod p,P,X) mod p;
%Gcd(A,P) mod p;
%B:=Rem(Powmod(Q,(p-1)/2,P,X)+1 mod p,P,X) 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 5 essais ce facteur est toujours $d$, elle retourne alors $d$.
% unfacteur:=proc(d)
% i:=1;
% A:=1;B:=1;rep:=1;
% #r:=rand(1..nops(N))();
% while (i<nops(N) and degree(rep)=0 ) do
% Q:=(LX.N[i])[1];
% 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,X)-1 mod p,P,X) 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,X)+1 mod p,P,X) mod p;
% A:=Gcd(A,d) mod p;
% if degree(A)*(degree(A)-degree(d))<>0 then rep:=A fi;
% fi;
% fi;
% i:=i+1;
% od;
% if degree(rep)=0 then d else rep  fi;
% end proc;
% 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$. 
% facteurpseudoirred:=proc(d)
% t:=unfacteur(d);
% tt:=d;
% while (degree(t)<degree(tt)) do tt:=t;t:=unfacteur(t); od;
% t;
% end proc;
% facteurpseudoirred(P);
\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?
%T:=P;a:=1;L:=[];
%while degree(T)>0 do T:=Quo(T,a,X) mod p;L:=[op(L),a];a:=facteurpseudoirred(T); od:L;
%#le nombre de facteurs doit etre la dim de ker F
% if nops(N)=nops(L)-1 then print("on a bien trouve tous les facteurs") fi;
\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\exotitre{Remont{\'e}e Henselienne}
On peut prendre le polyn{\^o}me $P$ pr{\'e}c{\'e}dent
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]$
% A:=L[2];B:=Quo(P,A,X) mod p; U:='U':V:='V':Gcdex(A,B,X,'U','V') mod p:
%# verification:
% Rem(A*U+B*V,P,X) mod p;
%#(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];
\qu Obtenir un diviseur de $P$ dans $\rela/p^2\rela[X]$ congru {\`a} $A$
modulo $p$.
% A:=L[2];B:=Quo(P,A,X) mod p; U:='U':V:='V':Gcdex(A,B,X,'U','V') mod p:
% # AU+BV=1[P];AB=P[p^i];(A+p^iAA)(B+p^iBB)=P[p^(i+1)]
% for i from 1 to 1 do
% PP:=expand((P-A*B)/p^i);AA:=Rem(PP*V,A,X) mod p;
% BB:=Quo(expand(PP-B*AA),A,X) mod p;
% A:=expand(A+p^i*AA);B:=expand(B+p^i*BB);
% A;
% od;
\qu Faire une proc{\'e}dure \code{remontee} qui {\`a} $A,B,P,i$ tels que
$AB=P[p]$, ($A\wedge B=1$) trouve $A,B$ tels que $AB=P[p^i]$ 
% remontee:=proc(AAA,BBB,P,j)
% #pour minimiser la valeur absolue des coeff:
% `mod`:=modp;
% A:=AAA;B:=BBB;
% Gcdex(A,B,X,'U','V') mod p:
% # AU+BV=1[P];AB=P[p^i];(A+p^iAA)(B+p^iBB)=P[p^(i+1)]
% for i from 1 to j do
% PP:=expand((P-A*B)/p^i);AA:=Rem(PP*V,A,X) mod p;
% BB:=Quo(expand(PP-B*AA),A,X) mod p;
% A:=expand(A+p^i*AA) mod p^(i+1);B:=expand(B+p^i*BB) mod p^(i+1);
% od;A,B;
% end proc;
\qu Obtenir un diviseur de $P$ dans $\rela[X]$
% A:=L[2];B:=Quo(P,A,X) mod p;remontee(A,B,P,10);
% #Ne convient pas forcement, il faut alors essayer d'autres facteurs,
% # ou bien des produits. Si la factorisation modulo $p$ a trop de
% #facteurs c'est plus long.
% for i from 2 to nops(L) do
% A:=L[i];B:=Quo(P,A,X) mod p;S:=remontee(A,B,P,10)[1];
% if abs(subs(X=0,S))<1000 then print("On pourrait essayer:",S);
% if rem(P,A,X)=0 then print(A,"est un diviseur dans Z") fi;
% fi;
% od:
\qu Quel est $max_i C^i_m$? Faire une proc{\'e}dure 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}$.
%borne:=proc(m,P)
%A:=Matrix([coeffs(P)]);
%binomial(m,floor(m/2))*evalf(sqrt((A.Transpose(A))[1,1]),5);
%end proc;
%borne(5,P),evalf(p^10,3);

    
\newpage
\end{multicols}

\end{document}
