\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} TP13 Corps finis\hspace{1cm}}\hfill   agreg 2009 (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(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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\F{{\rm I\! F}}
\exo 
\qu Trouver dans la documentation de xcas une instruction permettant de cr\'eer un
corps  fini, et de travailler dedans. Par exemple, cr\'eer un corps $\F_3[a]$
isomorphe \`a $\F_{3^6}$. Calculer $(1+a)^{17}$,
% F729:=GF(3,6,'a');
% F729((1+a)^17);
% a:=F729(a); #On note a cette classe.
% (1+a)^17
\qu Factoriser $x^3-x+1$ dans $\F_3$ et $F_{3^6}$, et $x^3-x+a$ dans $F_{3^6}$.
% Factor(x^3-x+1) mod 3;
% factor(x^3-x+1,a);
% factor(x^3-x+a,a);
\qu Trouver en utilisant  \code{Factor} un polyn\^ome irr\'eductible de degr\'e
$5$. Arrivez vous \`a cr\'eer $\F_{3^{20}}$
% Factor(x^{3^5}-x) mod 3;
% GF(3,20,a); #trop gros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotitre{polyn\^omes irr\'eductibles}
\qu Factoriser $X^8+1$ sur $\rela$ et sur $\F_3$
% Factor(X^8+1) mod 3;
\qusqu On consid\`ere l'ensemble \verb/l:={1,2,3,4,3,4};/ Remarquer que
la diff\'erence avec \verb/l:=[1,2,3,4,3,4];/ et obtenir le
compl\'ementaire de $\{1,3\}$ dans $l$ ainsi que celui de $l$ dans $l$.
% l:={1,2,3,4,3,4};
% l minus {1,3};
% l minus l;
\squ Soit $n$ un entier premier avec $3$. Faire une proc\'edure qui
affiche les orbites de $<3,.>$ agissant sur $\rela/n\rela$ par multiplication.
%!s!<p>
% orbites:=proc(n)
% local a,i,j,k,l,o,liste;
% liste:=[];
% if n mod 3 =0 then print("Erreur: 3 divise",n)
% else
% l:={seq(i,i=0..n-1)};
% j:=1;
% while l<>{} do
% i:=l[1];
% o:={i};a:=(3*i) mod n;
% while a<>i do o:=o union {a};a:= (3*a) mod n; od;
%%attention avant versions 31/1/2008 mettre un eval devant le minus
% l:= (l minus o); liste:=[op(liste),o]; 
% od;
% fi;
% liste;
% end proc;
%!s!
\squ Pour plusieurs valeurs de $n$, comparer ces orbites avec la
factorisation de $X^n-1$ dans $\F_3[X]$
% Factor(X^32-1) mod 3;
% orbites(32);
% Factor(X^14-1) mod 3;
% orbites(14);
%!s!<c>
% On remarque que pour tout i il y a autant d'orbites \`a i elements que de facteurs irreductibles de degre i
%!s!
\squ Pour $n$ allant de $1$ \`a $8$, quel est l'ordre de $3$ dans
$(\rela/2^n\rela)^\times$? Ce groupe est il cyclique? Commentez avec
le cas g\'en\'eral. 
% for i from 1 to 8 do print(nops(orbites(2^i)[2]),2^i) od;
\squ Quel est l'ordre maximal d'un \'el\'ement de
$(\rela/2^n\rela)^\times$? (NB: ce groupe se surjecte sur
$(\rela/4\rela)^\times$)
%!s!<c>
%  (Cf cours)On peut montrer que le noyau de la surjection donn\'ee par la
% reduction mod 4 est cyclique d'ordre 2^(n-2)
% -3=1+4.m ou m est impair, donc -3 est d'ordre maximal donc 3 aussi.
%  En fait les elements d'ordre max sont ceux congrus a 5 ou -5 mod 8
%!s!
\squ Pour ces $n$, factoriser sur $\rela$ $X^{2^n}-1$. Quels sont les
polyn\^omes cyclotomiques $\Phi_{2^n}$? Sont ils irr\'eductibles sur
$\F_3[X]$?
% for i from 1 to 8 do print(factor(X^(2^i)-1),2^i) od;
%!s!<c>
% le poly cyclo Phi_2^n est phi(n)
%!s!
% phi:=n->X^(2^(n-1))+1;
% for i from 1 to 8 do print(Factor(phi(i)) mod 3) od;
\qu Trouver un $i$ pour que $3^i-1$ soit divisible par $2^8$ mais pas
par $2^9$. On notera $q$ cette valeur de $3^i$.
% for i from 1 to 100 do if ((3^i-1) mod 2^8) == 0  then print(i) fi; od;
%!s!<c>
%on prend i=64
%!s!
\qu Trouver un polyn\^ome $P$ irr\'eductible de degr\'e $i$ dans $\F_3[X]$, o\`u $i$ est
la valeur choisie dans la question pr\'ec\'edente.
% Factor(X^128+1) mod 3;
% P:=X^64+X^32-1;
%% `mod`:=mods; # ne marche pas sous xcas
% Factor(P) mod 3; #P convient

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
% !s!<c>
%----------------Racines carrees---------------------------------------------------------------------------
%!s!
\exotitre{Racine carr\'ee dans $\F_q$}
\qusqu Faire une fonction \code{puiss} qui calcule la puissance
$n$-i\`eme d'un \'el\'ement $g$ de $\F_{q}$ o\`u $q=3^i$ , o\`u $i$ est l'entier fix\'e
que vous avez choisi dans l'exercice pr\'ec\'edent, et o\`u $n$ peut \^etre grand. (On
n'utilisera pas \code{GF}). On fera cette fonction 2 fois. Une o\`u l'on
programme les puissances rapides, l'autre ou l'on utilise \code{powmod}. 
% P:=x^64+x^32-1;
% !s!<p>
% puiss:=proc(g,n)
% local u,v;
% u:=1;v:=g;
% while n>1 do
% if (n mod 2 )==0 then v:=Rem(v*v,P) mod 3; n:=n/2;
% else u:=Rem(u*v,P) mod 3; v:=Rem(v*v,P) mod 3; n:=(n-1)/2;
% fi;od;
% Rem(u*v,P)mod 3;end;
%!s!
% puiss(1+x,5^7);
% puiss:=(g,n)->powmod(g,n,3,P,x);
% puiss(1+x,5^7); # on v\'erifie
\squ Faire une proc\'edure \code{testcarre} qui teste si $g$ est un carr\'e
dans  $\F_q$.
% q:=3^64;t:=(q-1)/2^8;
%!s!<m>
% testcarre:=proc(g)
% evalb(puiss(g,(q-1)/2)=1);
% end proc;
%!s!
\squ Trouver un \'el\'ement $g$ d'ordre $2^8$ dans $(\F_q)^\times$. 
% testcarre(1+x); # 1+x ne convient pas
% testcarre(1+x^5); # 1+x^5 n'est pas un carre donc g est d'ordre 2^8.
% g:=puiss(1+x^5,t); # verification:
% b:=[];
% for i from 0 to 8 do b:=[op(b),puiss(g,2^i)] od;
\squ Faire une fonction \code{inve} pour caluler un inverse dans
$\F_q$.
%!s!<m>
% inve:=proc(v)
% puiss(v,q-2)
% end proc;
%!s!
\squ Prendre un \'el\'ement $z$ de $\F_q$ qui soit un carr\'e.
% z:=1+x;testcarre(z);
\squ Trouver $z_1$ et $z_2$ tels que $z=z_1.z_2$ et $z_1$ soit d'ordre un
diviseur de $2^8$ et $z_2$ d'ordre impair. V\'erifier votre r\'esultat.
% (u,v):=igcdex(t,2^8)[1..2];
%!s!<c>
% dans cet exemple u est negatif, on cherche donc l'inverse de z
%!s!
% z1:=puiss(inve(z),-u*t);
% z2:=puiss(z,v*2^8);
%!s!<c>
% verification de l'isomorphisme  produit on doit retrouver z:
%!s!
% Rem(z1*z2,P) mod 3;z;
% !s!<c>
% On n'etait pas oblig\'e de trouver l'inverse de z, on utilise que z^(q-2)*z=1
% !s!
% z1:=puiss(z,(u*t) mod (q-1));
% Rem(z1*z2,P) mod 3;z; #attention, pour Rem mod il faut des x
\squ  Calculer la racine carr\'ee de $z_2$ puis de $z_1$, et obtenir une racine
carr\'ee de $z$.
% !s!<c>
%on verifie d'abord si q+1 est divisible par 4, si oui c'est tres simple.
%!s!
% (q+1) mod 4; #tant pis..
% racinez2:=puiss(z2,(t+1)/2);  #racine de z2:
% puiss(racinez2,2);z2;  #verification:
% m:=[seq(0,8)];xx:=z1; #on sauve z1
%!s!<m>
% for i from 7 to 0 by -1 do if Rem(puiss(z1,2^i)+1,P) mod 3 = 0 then
% m[8-i]:=1;z1:=Rem(z1*inve(b[8-i]),P) mod 3; else m[8-i]:=0;fi od;
%!s!
%!s!<c>
% verification:
%!s!
% z1:=1; for i from 1 to 8 do z1:=Rem(z1*puiss(b[i],m[i]),P) mod 3 od: z1;xx;#on verife que l'on trouve bien la valeur sauvee.
% racinez1:=1;for i from 2 to 8 do racinez1:=Rem(racinez1*puiss(b[i-1],m[i]),P) mod 3  od:puiss(racinez1,2);z1;
% racinez:=normal(Rem(racinez1*racinez2,P) mod 3);
% puiss(racinez,2);z;
\exotitre{Ordre d'un \'el\'ement}  
\qu Comment r\'ecup\'erer la liste des facteurs premiers d'un entier?
% !s!<c>
% Pour avoir la matrice (nombre premier, multiplicite), on utilise en mode xcas
% maple_ifactors. En mode maple  ifactors coincide avec maple_ifactors. 
% !s!
% maple_ifactors(36*7)[2];
% ifactors(36*7)[2];
% transpose(ifactors(36*7)[2])[1];
\qu Faire une proc\'edure \code{ord(x,n)} calculant l'ordre d'un \'el\'ement $x$ de
$(\rela/n\rela)^\times$. On partira d'un \'el\'ement $m$ tel que $x^m=1 [n]$. On
s'arrangera pour qu'un \'el\'ement de petit ordre soit trouv\'e rapidement. Par
exemple l'ordre de $-1$ dans $(\rela/2^{1000}\rela)^\times$. (On utilisera une
fonction de puissance rapide modulaire deja programm\'ee).
% !s!<p>
% ordre:=proc(x,n)
% local m,l,p,y;
% m:=Phi(n);
% l:=(maple_ifactors(m)[2]);
% for i from 1 to rowdim(l) do
% m:=iquo(m,l[i,1]^l[i,2]);y:=powmod(x,m,n);
% while y <> 1 do y:=powmod(y,l[i,1],n);m:=m*l[i,1]; od;
% od;
% m;
% end;
% !s!
% ordre(-1,2^1000);
% pari();
%!s!<m>
% if (pari_znorder(Mod(5,11^5*2^40*101)) == ordre(5,11^5*2^40*101)) then
% print("ca marche") else print("il y a une erreur") fi;
% !s!
%
\newpage
\end{multicols}

\end{document}

