\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 Anneaux $Z/nZ$\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
\exotitre{Puissances rapides.}
\qusqu Afin d'\'evaluer la fa\c con dont votre logiciel calcule une puissance, sans \^etre
perturb\'e par des probl\`emes de taille, testez des grandes puissances d'entiers
modulaires, et trouver \'eventuellement\footnote{plutot pour les utilisateurs
  maple} la "bonne" instruction.
\squ Pour diff\'erentes valeurs de $n$, \'etudiez le temps de calcul $t_n$ de $27^(2^n)
[107]$. Repr\'esentez sur un dessin des couples $(n,t_n)$ pour illustrer le co\^ut.
% l:=[];
% for n from 10^4 to 10^5 by 1000  do l:=[op(l),[n,time(27^(2^n) mod 107)]] ; od;
% !s!<c>
% Le coup semble lineaire (en n) sur ce dessin, ce qui illustre bien que le
% calcul de 27^A est en O(ln(A))
%!s!
% plotlist(l);
\qu Cr\'eer une proc\'edure \verb/puis:=proc(a,n)/ qui calcule $a^n$
par une m\'ethode rapide. On essayera de ne pas calculer \`a priori l'\'ecriture en
base $2$ de $n$. 
% !s!<c>
% -------------------------------------EXERCICE-----------------------------------------
% !s!<c>
% !s!<p>
% puis:=proc(a,n)
% local A,B,C;
% A:=1;B:=a;C:=n;
% while C>0 do
% if irem(C,2)=1 then A:=A*B;C:=(C-1)/2;B:=B*B;
% else C:=(C)/2;B:=B*B;
% fi;
% od;
% A;
% end;
% !s!
% puis(2,7);
\qusqu En utilisant \code{debug(puis(2,71))}, \'etudier les valeurs de
$A,B,C$. (utiliser le bouton \code{watch}, et regarder la valeur de la
variable tout en bas.)
% debug(puis(2,71));)
\squ Comparer les passages dans vos tests avec l'\'ecriture en base 2 de
$n$. Comment trouver cette \'ecriture avec votre logiciel?
% convert(71,base,2);
% !s!<c>
%-------------------------------------------------------------------------------------------------
%!s!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\exotitre{utilisation de pari}
Pour pouvoir utiliser les instructions pari sous xcas on tapes \code{pari();}
\qu Trouvez dans la documentation les fonctions pari disponibles pour les groupes
$(\rela/n \rela)^\times$.
\qu Etudiez le temps de calcul pour trouver une racine primitive dans
$\rela/p\rela$ pour divers $p$ premiers.
%pari();
% p:=nextprime(2^256);
%znprimroot(p);
% p:=nextprime(2^256+987654327);
%znprimroot(p);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotitre{Ecrit 2007}
% !s!<c>
% -------------------------------------EXERCICE---------------------------------------------
%!s!
\qu Choisir un nombre premier $p$ \`a 13 chiffres, tel que le probl\`eme
du log discret soit difficile modulo $p$. (Cf exercice pr\'ec\'edent)
% p:=l[3];
\qu Choisir un entier $b$ et rendre publique $(b,b^e [p])$. Commentez
votre choix de $b$.
% !s!<c>
% b,e pas trop petits par rapport a p, pour que le modulo p melange
% vraiment.
%!s!
\qu Remarquer que les lettres $A\dots Z$ ont des codes ASCII
cons\'ecutifs. Comment obtenir les codes de chaque lettre d'un mot? (et
si l'on veut que $A$ soit repr\'esent\'e par $0$ et $Z$ par $25$?)
% message:="ABCDA, Remarquez que des lettres identiques ne sont pas codees de la meme maniere!";asc(message);
% asc(messsage)-[seq(65,i=1..length(message))];
\qu Votre voisin choisit un message, tire des $k$ au hasard et code
chaque lettre $x$ avec $(b^k [p],x.(b^e)^k) [p])$ (sans connaitre $e$,
seulement avec $b$ et $b^e$
% b:=12345;e:=54321; igcd(e,p-1); B:=powmod(b,e,p);
% l:=asc(message);k:=[seq(rand(50),i=1..length(message))];
% C:=[seq([(b^k[i]) mod p,(l[i]*B^k[i]) mod p],i=1..length(message))];#le message crypte
\qusqu D\'ecoder le message gr\^ace \`a $e$.
%ee:=p-1-e;#c'est -e [p-1] qui nous interesse 
% !s!<c>
% L'astuce est que (B^k)=((b^e)^k) qui vaut par commutativit\'e  des la
% composition des application B:x->x^k et A:x->x^e  ((b^k)^e). 
%Le principe a retenir, est qu'en crypto on a juste besoin
%d'operations A,B qui  commutent, et que la donnee de A de donne pas
%A^(-1)  
%!s!
% decrypt:=[seq(irem(powmod(C[i][1],ee,p)*C[i][2],p),i=1..length(message))];
% char(decrypt);
\squ Pr\'eparer un  expos\'e de 15 minutes expliquant la m\'ethode et son
int\'er\^et. (temps pour crypter, d\'ecryper avec et sans $e$. Statitiques
sur les lettres du message crypt\'e...)
\newpage
\end{multicols}

\end{document}

