\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{0.5cm} S\'eance 14 $(\rela/p\rela)^\times$ II\hspace{0.5cm}}\hfill   agreg 2011 (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(0);cas_setup(0,0,0,1,0,1e-10,10,[1,50,0,25],0,0,0); //radians,pas de cmplx, pas de  Sqrt
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% !s!<c>
% ------------------------------------------------Exercice---------------------------------------------
%!s!  
\exotitre{Rabin-Miller}
Le test primalit\'e de Rabin-Miller pour un entier $n$: S'il existe $a$ et $i\geq
1$ tels que 
$2^i$ divise $n-1$ et que l'on ait $a^{\frac{n-1}{2^{i-1}}}=1[n]$ avec
$a^{\frac{n-1}{2^i}}\neq \pm 1[n]$, alors $n$ n'est pas premier.
\qu Quelle fonction utiliser pour une puissance rapide modulaire? Etudiez par
cette m\'ethode la valeur de retour de $(-1)^{101} [7]$ et de $(-1)^{101}[p]$ o\`u
$p$ est grand.
\qu Cr\'eez d'abord une fonction \code{ramil1(n)} qui effectue ce test mais en
utilisant pour l'instant qu'un seul t\'emoin $a$. (On prendra par exemple
$a=2$). On \'evitera de devoir factoriser  $n-1$.
% n:=nextprime(10^13)*nextprime(12^14)*nextprime(10^7);
%!s!<p>
%rabmil1:=proc(n)
%local m,j0,a,b,retour;
%//retour vaut 0 si l'on ne sait pas si n est premier.
%//retour=1 implique que l'on est sur que n n'est pas premier.
%retour:=0;
%j0:=0;m:=n-1;a:=2;
%while(irem(m,2)==0){m:=m/2;j0++};
%b:=powmod(a,m,n);j:=0;
%while((irem((b-1)*(b+1),n) <> 0) and j<j0){b:=irem(b*b,n);j++;};
%if (b==1 and j>0)then retour:=1;
%          else if (j==j0) then retour:=1; fi;
%          fi;
%retour;
%end;
%!s!
%!s!<p>
%rabmil2:=proc(n)
%local m,j0,a,b,retour;
%//retour vaut 0 si l'on ne sait pas si n est premier.
%//retour=1 implique que l'on est sur que n n'est pas premier.
%retour:=0;
%j0:=0;m:=n-1;a:=2 % n;
%while(irem(m,2)==0){m:=m/2;j0++};
%b:=a^m;j:=0;
%while((b != 1 % n) and (b!=-1 % n) and j<j0){b:=(b*b);j++;};
%if (b==1 % n and j>0)then retour:=1;
%          else if (j==j0) then retour:=1; fi;
%          fi;
% retour;
%end;
%!s!
\qu Pour une valeur de $n$ de votre choix (non premi\`ere), donner toutes les
valeurs de $a$ pour lesquelles on n'a pas de r\'eponse sure. Comparer ce nombre
avec $phi(n)/4$. 
%!s!<p>
% testa:=proc(n)
%local m,j0,a,b,retour;
%//retour vaut 0 si l'on ne sait pas si n est premier.
%//retour=1 implique que l'on est sur que n n'est pas premier.
%retour:=0;
%j0:=0;m:=n-1;
% while(irem(m,2)==0){m:=m/2;j0++};
% l:=[ ];
%for(a:=2;a<n;a++)
% {
%   retour:=0;
%  b:=(a % n )^m;j:=0;
%  while((b != 1 % n) and (b!=-1 % n) and j<j0){b:=(b*b);j++;};
%  if (b==1 % n and j>0)then retour:=1;
%          else if (j==j0) then retour:=1; fi;
%          fi;
%          if(retour==0){l:=augment(l,a)};
%        }
% l;
%end;
%!s!
%
\qu Si la probalilit\'e d'avoir un mauvais t\'emoin est major\'ee par $1/4$, combien
de temoins faut il utiliser pour avoir une r\'eponse sure a $99.9\%$
% !s!<c>
% Il faut n tel que: (0.25)^n < 0.001 et donc n superieur a:
% !s!
% ln(0.001)/ln(0.25)
\qu Programmez un test de rabin-miller avec cette fiabilit\'e.
%!s!<p>
% rabmil:=proc(n)
%local m,j0,a,b,retour;
%//retour vaut 0 si l'on ne sait pas si n est premier.
%//retour=1 implique que l'on est sur que n n'est pas premier.
%retour:=0;
%j0:=0;m:=n-1;
% while(irem(m,2)==0){m:=m/2;j0++};
% l:=[2,101,55,23,177];
%for(ia:=0;ia<5;ia++)
% {
%   retour:=0;a:=l[ia];
%  b:=(a % n )^m;j:=0;
%  while((b != 1 % n) and (b!=-1 % n) and j<j0){b:=(b*b);j++;};
%  if (b==1 % n and j>0)then retour:=1;ia:=5
%          else if (j==j0) then retour:=1; ia:=5;fi;
%          fi;
%  }
% retour;
%end;
%!s!
%rabmil(561)
%n:=nextprime(10^13)*nextprime(5^22)*nextprime(9^11);
%rabmil(n);
%rabmil(nextprime(444444444444444))
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exo finir TP13 sur log discret.
\newpage
\end{multicols}
\end{document}

