\documentclass[12pt,a4paper]{article}
\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} TP3 \hspace{1cm}}\hfill   agreg 2007 (F.Han)}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 

\noindent\begin{minipage}[t]{0.46\textwidth}
% interface(screenwidth=120);
  \exo
  \qu Comparer \verb/2^1000000000000 mod 7; / et
  \verb/2&^1000000000000 mod 7;/
% 2^1000000000000 mod 7; # la puissance est faite dans Z
% 2&^1000000000000 mod 7;# c'est mod qui calcule la puissance.  
  \qusqu Etudier \code{[1,3,1];} et \verb/{1,3,1};/ et leur cardinal.
% [1,3,1],nops([1,3,1]); # est une suite ou liste
% {1,3,1},nops({1,3,1}); # est un ensemble, il est donc egal {\`a} {1,3}
  \squ Trouver un moyen pour enlever les
crochets d'une suite, et en d{\'e}duire une fa\c con d'ajouter un
{\'e}l{\'e}ment {\`a} une liste. (Cf \code{op})(A RETENIR!)
%l:=[];# voici la liste vide;
%l:=[op(l),1]:l:=[op(l),3]:l:=[op(l),1]:l;
\exo
Nous voulons\footnote{r{\'e}f: D. Knuth: The art of computer programming:
  chapter 3 (tout d{\'e}but du vol 2)} cr{\'e}er une fonction pseudo al{\'e}atoire
gr{\^a}ce {\`a} une suite r{\'e}curente. C'est souvent dangereux de prendre une
fonction compliqu{\'e}e 
qui ne permette pas d'analyser le comportement de la suite. Nous
allons donc essayer de prendre congruences lin{\'e}aires: $x_{n+1}=a.x_n+c
 \ [m]$.
\qu Nous voulons montrer que le cas $a=1$ est tr{\`e}s mauvais. (ne
parlons pas de $a=0$).
% #Si a=1, on a x_n=x_0+n.c [m], on fait donc par exemple: c=7,x0=1
\squ Tracer l'histogramme des fr{\'e}quences pour $x_{n}=7.n+1 [1000]$
pour 100 valeurs.
%with(stats):with(statplots):
%l:=[seq(n.7+1 mod 1001,n=1..100)]:
%histogram(l,area=count,numbars=20);
%#C'est tout a fait plat. Trop.
\squ
%nops(l);nops({op(l)}); #ils sont tous distincts
\squ En utilisant une fonction al{\'e}atoire du logiciel, cr{\'e}er une suite
  de 100 termes entre 0 et 1000. Tracer les histogrammes {\`a} 5 et 20
  colonnes. Comparer avec la question pr{\'e}c{\'e}dente. 
% r:=rand(0..1000);
% l:=[seq(r(n),n=1..100)]:
% histogram(l,area=count,numbars=5);
% histogram(l,area=count,numbars=20);
%#Remplacer les crochets par des incolades cree un ensemble.  
% nops(l);nops({op(l)});#il y a bien des anniversaires identiques
  \squ Trouver un moyen rapide de compter le nombre de valeurs {\'e}gales
  dans la liste (Ex convertir la liste en ensemble). Combien en trouve
  t'on avec la fonction al{\'e}atoire du   logiciel?
  \squ Donner une valeur approch{\'e}e de la probabilit{\'e} pour que nos 100
  tirages soient distincts. Conclure que le cas $a=1$ ne passe pas le
  test des anniversaires.
% #On a en fait 1000^100 suites possibles, et 1000!/900! suites dont
% #tous les termes sont distincts.
% 1000!/900!/1000.^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$.
\end{minipage}
\hfill
\begin{minipage}[t]{0.46\textwidth}
\qu Le choix de $m$. Nous cherchons maintenant un $m$ {\`a} la fois bon
pour le comportement al{\'e}atoire 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{\'e}partition 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(l1,area=count,numbars=10);
%histogram(l2,area=count,numbars=10);
%l1:=[seq(i mod 10,i=l)]:
%histogram(l1,area=count,numbars=10);
%#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{\'e}riode d'au plus d.
\squ On prend donc dans la suite $m=w\pm 1$, ou bien le plus grand
nombre premier inf{\'e}rieur {\`a} $w$. Le probl{\`e}me 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(l1,area=count,numbars=10);
% histogram(l2,area=count,numbars=10);
% l1:=[seq(i mod 10,i=l)]:
% histogram(l1,area=count,numbars=10);
% 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(l1,area=count,numbars=10);
% histogram(l2,area=count,numbars=10);
% l1:=[seq(i mod 10,i=l)]:
% histogram(l1,area=count,numbars=10);
\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(l,area=count,numbars=10);#certaines valeurs ne sont pas atteintes.
\qu De m{\^e}me, on essaie de  choisir  $a$ pour que $a^n [m]$ ait une
grande p{\'e}riode.
\squ Lemme: Montrer que si $m\wedge m'=1$, alors la p{\'e}riode de
$x_{n+1}=a.x_n+c \ [m.m']$ est le ppcm des p{\'e}riodes 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{\'e}riodes 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,.) $
%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;
% #verification
% periode(1),periode(5);
% l:=seq(periode(i),i=2..124);max(l);
% #On a: x_n=(a^n-1)/(a-1) mod m, donc la periode est l'ordre de a.
\squ Th{\'e}or{\`e}me: Soit $x_0=0,x_{n+1}=a.x_n+c \ [m]$, alors $(x_n)$ est
de p{\'e}riode 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 {\'e}l{\'e}ment du
groupe multiplicatif de $\rela/(a-1)m\rela$ et la p{\'e}riode est l'ordre
de $a$ dans ce groupe.
\end{minipage}
\end{document}
