\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} TP09 Anneaux $Z/nZ$\hspace{1cm}}\hfill   agreg 2010 (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.
% !s!<c>
%Sous xcas la puissance modulaire n'est pas toujours donne les memes temps que powmod, elle
%ne semble donc pas toujours bien faite. Attention, sous le logiciel maple ca n'est pas le cas,
%il faut mettre un ^&
%!s!
%N:=3^(10^6); # On calcule le N avant pour qu'il ne soit pas pris en compte dansle temps 
% time(powmod(33,N,107));
% time(33^N mod 107); #la ca marche
% N:=6700000
% time(powmod(33,N,107));
% time(33^N mod 107); #la c'est bien plus long
\squ Pour diff\'erentes valeurs de $n$, \'etudiez le temps de calcul $t_n$ de $27^{(2^n)}
[107]$. Repr\'esentez sur un m\^eme dessin une liste de couples $(n,t_n)$ ainsi que
la droite de r\'egr\'ession lin\'eaire de cette famille, pour illustrer le co\^ut. Quel
est le coefficient de correlation?
% 
% !s!<c>
% -------------------------------------EXERCICE-----------------------------------------
% !s!
% 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!
% rl:=[linear_regression(l)];
% plotlist(l);droite(y=rl[1]*x+rl[2],couleur=green);
% !s!<c>
%On aurait pu utiliser directement linear_regression_plot pour faire le dessin.
% !s!
% correlation(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!<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>
%--------------------------------------Exercice---------------------------------------------------
%!s!
\exotitre{fonctions random}
\qu \danger Sous xcas, \'etudier: \code{8*2+7 mod 7;}
%8*2+7 mod 7; (8*2+7) mod 7; #Attention mod est prioritaire sous xcas
Nous voulons\footnote{r\'ef: D. Knuth: The art of computer programming:
  chapter 3 (tout d\'ebut du vol 2)} cr\'eer une fonction pseudo al\'eatoire
gr\^ace \`a une suite r\'ecurrente. C'est souvent dangereux de prendre une
fonction compliqu\'ee 
qui ne permette pas d'analyser le comportement de la suite. Nous
allons donc essayer de prendre congruences lin\'eaires: $x_{n+1}=a.x_n+c
 \ [m]$.
\qu Nous voulons montrer que le cas $a=1$ est tr\`es mauvais. (ne
parlons pas de $a=0$).
%!s!<c>
% Si a=1, on a x_n=x_0+n.c [m], on fait donc par exemple: c=7,x0=1
%!s!
\squ Tracer l'histogramme des fr\'equences pour $x_{n}=7.n+1 [1000]$
pour 100 valeurs.
%l:=[seq((n*7+1) mod 1001,n=1..100)];
%histogram(classes(l,0,1001/20)); #C'est tout a fait plat. Trop!
\squ
%!s!<c>
% Remplacer les crochets par des incolades cree un ensemble, ce qui simplifie
% automatiquement les elements egaux  
%!s!
% nops(l);nops({op(l)}); #ils sont tous distincts
\squ En utilisant une fonction al\'eatoire du logiciel, cr\'eer une suite
  de 100 termes entre 0 et 1000. Tracer les histogrammes \`a 5 et 20
  colonnes. Comparer avec la question pr\'ec\'edente. 
% l:=[seq(rand(1001),n=1..100)];
% histogram(classes(l,0,1001/5));
% histogram(classes(l,0,1001/20));  
% nops(l);nops({op(l)});#il y a bien des anniversaires identiques
  \squ Trouver un moyen rapide de compter le nombre de valeurs \'egales
  dans la liste (Ex convertir la liste en ensemble). Combien en trouve
  t'on avec la fonction al\'eatoire du   logiciel?
  \squ Donner une valeur approch\'ee de la probabilit\'e pour que nos 100
  tirages soient distincts. Conclure que le cas $a=1$ ne passe pas le
  test des anniversaires.
%!s!<c>
% On a en fait 1001^100 suites possibles, et 1001!/901! suites dont
% tous les termes sont distincts.
%!s!
% 1001!/901!/1001.^100;
\squ Dans la suite on supposera $a>1$. On pose alors $b=a-1$. On
  remarquera que $$x_{n+k}=a^k x_n +(a^k-1)c/b \ [m]$$ et que $
  x_n=Ay_n+1 [m]$ o\`u $y_0=0, y_{n+1}=ay_n+1 \ [m]$ et $A=ax_0+c \
  [m]$, ce qui permet de calculer simplement $x_n$ en fonction du cas $c=1$.
\qu Le choix de $m$. Nous cherchons maintenant un $m$ \`a la fois bon
pour le comportement al\'eatoire et pour le temps de calcul. On prend
donc $m$ proche de la taille $w$ d'un mot de l'ordinateur. Ex $m$ proche
de $2^e$ s'il travaille sur $e$-bits. Pour simplifier ici on
travaillera en base $10$. 
\squ Montrons maintenant que le choix de $m=w$ est mauvais. Etudier la
r\'epartition des $2$ derniers chiffres de $x_n$ par rapport aux $2$
premiers lorsque  l'on prend $e=4$. Etudier aussi le dernier
chiffre.
%x:=1; a:=237;c:=54321;m:=10^4; l:=[];
%for i from 1 to 500  do x:=(a*x+c) mod m; l:=[op(l),x] ; od:
%l1:=[seq(i mod 10^2,i=l)];
%l2:=[seq(trunc(i/10^2),i=l)];
%histogram(classes(l1,0,5));
%histogram(classes(l2,0,5));
%l1:=[seq(i mod 10,i=l)];
%histogram(classes(l1,0,1));
%!s!<c>
%Si d est un diviseur de m et que $y_n=x_n [d]$, alors $y_{n+1}=ay_n+c [d]$
%Donc si d=10^2, les 2 derniers chiffres de x_n ont p\'eriode d'au plus d.
%!s!
\squ On prend donc dans la suite $m=w\pm 1$, ou bien le plus grand
nombre premier inf\'erieur \`a $w$. Le probl\`eme persiste t'il?
% x:=1; a:=237;c:=54321;m:=10^4-1; l:=[];
% for i from 1 to 500  do x:=(a*x+c) mod m; l:=[op(l),x] ; od:
% l1:=[seq(i mod 10^2,i=l)];
% l2:=[seq(trunc(i/10^2),i=l)];
% histogram(classes(l1,0,5));
%histogram(classes(l2,0,5));
% l1:=[seq(i mod 10,i=l)];
% histogram(classes(l1,0,1));
% x:=1; a:=237;c:=54321;m:=prevprime(10^4); l:=[];
% for i from 1 to 500  do x:=(a*x+c) mod m; l:=[op(l),x] ; od:
% l1:=[seq(i mod 10^2,i=l)];
% l2:=[seq(trunc(i/10^2),i=l)];
% histogram(classes(l1,0,5));
%histogram(classes(l2,0,5));
% l1:=[seq(i mod 10,i=l)];
% histogram(classes(l1,0,1));
\squ Comparer la fonction random obtenue en prenant le dernier chiffre
dans la question precedente \`a celle obtenue en passant tout de suite
modulo $10$.
%x:=1; a:=237;c:=54321;m:=10; l:=[];
%for i from 1 to 100  do x:=(a*x+c) mod m; l:=[op(l),x] ; od:
%histogram(classes(l,0,1)); #certaines valeurs ne sont pas atteintes.
\qu De m\^eme, on essaie de  choisir  $a$ pour que $a^n [m]$ ait une
grande p\'eriode.
\squ Lemme: Montrer que si $m\wedge m'=1$, alors la p\'eriode de
$x_{n+1}=a.x_n+c \ [m.m']$ est le ppcm des p\'eriodes de
$y_{n+1}=a.y_n+c \ [m]$ et de $z_{n+1}=a.z_n +c \ [m']$ (o\`u
$x_0=y_0=z_0$).
\squ Dans le cas o\`u $m=5^3$, donnez la liste des p\'eriodes possibles de
la suite: $x_0=0,x_{n+1}=a.x_n+1 \ [m]$ pour $m-1>a>1,a\wedge 5=1$. Quel est
l'ordre de $a$ dans $((\rela/(a-1).m\rela)^\times,.) $
%!s!<p>
% periode:=proc(a)
% x:=1;p:=1;
% if (a mod 5 <> 0) then while x>0 do p:=p+1;x:=(a*x+1) mod 125; od; fi;
% p; end proc;
%!s!
% periode(1),periode(5); #verification
% l:=seq(periode(i),i=2..124);max(l);
%!s!<c>
% On a: x_n=(a^n-1)/(a-1) mod m, donc la periode est l'ordre de a.
%!s!
\squ Th\'eor\`eme: Soit $x_0=0,x_{n+1}=a.x_n+c \ [m]$, alors $(x_n)$ est
de p\'eriode maximale ($m$) si et seulement si $c$ est
premier avec $m$, et $a=1[d]$ pour tout diviseur $d$ de $m$ tel que
$d$ soit premier impair ou $4$. Dans ce cas, $a$ est un \'el\'ement du
groupe multiplicatif de $\rela/(a-1)m\rela$ et la p\'eriode est l'ordre
de $a$ dans ce groupe.


\newpage
\end{multicols}

\end{document}

