\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 $\rela/n\rela$\hspace{1cm}}\hfill   agreg 2008 (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{Primalit{\'e}; temps de  calculs}
\qu Etudier  les fonctions \code{nextprime} et
\code{isprime}, \verb/is_pseudoprime/. Comparer les temps d'executions
pour des nombres {\`a} 20 chiffres. Etudier la documentation.
% time(p:=nextprime(10^50));
% time(isprime(p));
% time(is_pseudoprime(p));
% !s!<c>
% le temps de isprime est trop long pour avoir ete utilise pour
% trouver le nombre premier avec nextprime. La doc confirme bien que
% nextprime donne un pseudopremier.
%!s!
\qusqu Etudier:\\
\verb/n:=nextprime(10^i)*nextprime(20^i);/
Essayer de factoriser $n$ pour diff{\'e}rententes valeurs de  $i$. A partir de
quand est ce que ca ne r{\'e}pond plus?
% i:=20;n:=nextprime(10^i)*nextprime(20^i); 
% ifactor(n);
% !s!<c>
% a partir de i=30 ca ne repond plus?
% !s!
\squ Prendre des nombres premiers de cette taille. Etudier si l'on
arrive {\`a} factoriser $p-1$.
% p:=nextprime(=nextprime(10^30)*nextprime(20^30));
%ifactor(p-1); #ca marche souvent
\squ En utilisant pari, obtenir un certificat de primalit{\'e}  par la
m{\'e}thode de Lehmer (et al)  pour un nombre de cette taille. Interpr{\'e}ter
la r{\'e}ponse.
%pari();
%pari_isprime(p,1);
%!s!<c>
%Les grands nombres premiers apparaissant dans le certificat sont eux
%m{\^e}me certifi{\'e}s, ce qui explique les crochets emboit{\'e}s.
%!s!
\qu {\bf log discret:}
\squ Trouver une dizaine de nombres pseudopremiers du type $4p+1$ o{\`u} $p$
est un pseudopremier {\`a} au moins 13 chiffres. Est ce difficile de
trouver des nombres premiers tels que $p-1$ ait un grand facteur?
% p:=nextprime(10^13);i:=0;l:=[];
% !s!<m>
% while i<10 do
% if ispseudoprime(4*p+1)>0 then l:=[op(l),4*p+1];i++; fi;
% p:=nextprime(p);
% od:l;
% !s!
\squ Chercher dans pari les intructions pour trouver un g{\'e}n{\'e}rateur $g$
de $(\rela/n\rela)^\times$ lorsqu'il est cyclique. Trouver un
g{\'e}n{\'e}rateur $g$ de  $(\rela/p\rela)^\times$ o{\`u} $p$ vaut
\verb/\nextprime(10^13+100)/. En utilisant
\verb/pari_znlog(3,Mod(g,p))/ trouver $m$ tel que $3=g^m
[p]$. Expliquer pourquoi il a r{\'e}ussi?
%p:=\nextprime(10^13+100);
%g:=pari_znprimroot(p);
%pari_znlog(3,Mod(g,p)); #il reussit
%ifactor(p-1);
%!s!<c>
%p-1 a de petits facteurs premiers, on peut donc resoudre le probleme
%du log discret. Dans le cas suivant ca ne marche plus.
%!s!
\squ Recommencer avec un exemple du type $p=4q+1$ trouv{\'e} pr{\'e}cedemment.
% p:=l[3];
%g:=pari_znprimroot(p);
%pari_znlog(3,Mod(g,p)); #depasse la memoire max de pari
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\exotitre{(reprise TP00)}
% !s!<c>
% -------------------------------------EXERCICE---------------------------------------------
%!s!
\qu Choisir un nombre premier $p$ {\`a} 13 chiffres, tel que le probl{\`e}me
du log discret soit difficile modulo $p$. (Cf exercice pr{\'e}c{\'e}dent)
% 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{\'e}cutifs. Comment obtenir les codes de chaque lettre d'un mot? (et
si l'on veut que $A$ soit repr{\'e}sent{\'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{\'e}coder le message gr{\^a}ce {\`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{\'e}parer un  expos{\'e} de 15 minutes expliquant la m{\'e}thode et son
int{\'e}r{\^e}t. (temps pour crypter, d{\'e}cryper avec et sans $e$. Statitiques
sur les lettres du message crypt{\'e}...)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
% !s!<c>
%--------------------------------------Exercice---------------------------------------------------
%!s!
\exotitre{fonctions random}
\qu \danger Sous xcas, {\'e}tudier: \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{\'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}currente. 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$).
%!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{\'e}quences 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{\'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. 
% 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 {\'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.
%!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{\'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(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{\'e}riode d'au plus d.
%!s!
\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(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{\^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,.) $
%!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{\'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.


\newpage
\end{multicols}

\end{document}

