\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} TP10 \hspace{1cm}}\hfill   agreg 2007 (F.Han)}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
\columnsep 0.7cm
\begin{multicols}{2}
% interface(screenwidth=120);
\def\F{{\rm I\! F}}
\exotitre{Racine carr\'ee dans $\F_q$}
\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$
% 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.
% orbites:=proc(n)
% if n mod 3 =0 then print("Erreur: 3 divise",n) fi;
% l:={seq(i,i=0..n-1)};
% j:=1;
% while l<>{} do
% i:=l[1];
% o[j]:={i};k:=1;a:=0;
% while a<>i do a:= 3^k*i mod n;o[j]:={op(o[j]),a};k:=k+1; l:=l od;
% l:= l minus o[j]; j:=j+1: 
% od:seq(o[i],i=1..j-1);
% end proc;
\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);
% #On remarque que pour tout i il y a autant d'orbites a i elements que de facteurs irreductibles de degre i
\squ Pour $n$ allant de $1$ \`a $12$, 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 12 do nops(orbites(2^i)[2]),2^i end do;
\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$)
% # 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
\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 12 do factor(X^(2^i)-1),2^i od;
% #le poly cyclo phi_2^n est phi(n)
% phi:=n->X^(2^(n-1))+1;
% for i from 1 to 10 do 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; end
% do;
% #on prend i=64
\qu Trouver un polyn\^ome $P$ irr\'eductible de degr\'e $i$ dans $\F_3[X]$
% Factor(X^128+1) mod 3;
% P:=X^64+X^32-1;
% `mod`:=mods;
% Factor(P) mod 3;
% #P convient
\qusqu Faire une fonction \code{puissance} qui calcule la puissance
$n$-i\`eme d'un \'el\'ement $g$ de $\F_{q}$ o\`u $i$ est l'entier fix\'e
que vous avez choisi.
% puissance:=(g,n)->Powmod(g,n,P,X) mod 3;
\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;
% testcarre:=proc(g)
% evalb(puissance(g,(q-1)/2)=1);
% end proc;
\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:=puissance(1+X^5,t);
% # verification:
% b:='b';
% for i from 0 to 8 do b[i]:=puissance(g,2^i) od;
\squ Faire une fonction \code{inverse} pour caluler un inverse dans
$\F_q$.
% inverse:=proc(x)
% Gcdex(x,P,X,'invx','tutu') mod 3;
% invx;
% end proc;
\squ Prendre un \'el\'ement $z$ de $\F_q$ qui soit un carr\'e.
% z:=1+X;testcarre(z);
\squ Trouver $x$ et $y$ tels que $z=x.y$ et $x$ soit d'ordre un
diviseur de $2^8$ et $y$ d'ordre impair. V\'erifier votre r\'esultat.
% igcdex(t,2^8,'u','v');u,v;
% #dans cet exemple u est negatif, on cherche donc l'inverse de z
% Gcdex(z,P,X,'invz','tutu') mod 3;
% #verification de l'isomorphisme  produit on doit retrouver z:
% x:=puissance(inverse(z),-u*t);
% y:=puissance(z,v*2^8);
% Rem(x*y,P,X) mod 3;z;
\squ  Calculer la racine carr\'ee de $y$ puis de $x$, et obtenir une racine
carr\'ee de $z$.
% # on verifie d'abord si q+1 est divisible par 4, si oui c'est tres simple.
% q+1 mod 4;#tant pis..
% #racine de y:
% raciney:=puissance(y,(t+1)/2);
% #verification:
% puissance(raciney,2);y;
% m:='m';xx:=x;#on sauve x
% for i from 7 to 0 by -1 do if puissance(x,2^i)=-1 then
% m[7-i]:=1;x:=Rem(x*inverse(b[7-i]),P,X) mod 3; else m[7-i]:=0;fi od;
% # verification:
% x:=1; for i from 0 to 7 do x:=Rem(x*puissance(b[i],m[i]),P,X) mod 3
% od: x;xx;#on verife que l'on trouve bien la valeur sauvee.
% racinex:=1;for i from 1 to 7 do racinex:=Rem(racinex*puissance(b[i-1],m[i]),P,X) mod 3
% od:puissance(racinex,2);x;
% racinez:=Rem(racinex*raciney,P,X) mod 3;
% puissance(racinez,2);z;

    
\newpage
\end{multicols}

\end{document}
%%\begin{minipage}[t]{0.46\textwidth}
%%\end{minipage}
%%\hfill
%%\begin{minipage}[t]{0.46\textwidth}
%%\end{minipage}
