\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} TP12 Anneaux $\rela/n\rela$\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{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\'erententes valeurs de  $i$. A partir de
quand est ce que ca ne r\'epond 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
\qusqu En utilisant pari, obtenir un certificat de primalit\'e  par la
m\'ethode de Lehmer (et al)  pour un nombre de cette taille. Interpr\'eter
la r\'eponse.
%pari();
%pari_isprime(p,1);
%!s!<c>
%Les grands nombres premiers apparaissant dans le certificat sont eux
%m\^eme certifi\'es, ce qui explique les crochets emboit\'es.
%!s!
\squ En cr\'eant au hasard un nombre $n$ dont vous connaissez la factorisation,
trouver un nombre pseudopremier du type $n+1$ assez grand, et tentez de le
certifier vous m\^eme. 
% !s!<c>
% On a cree n avec de petits facteurs, on arrive a le factoriser
%!s!
% !s!<m>
% i:=0;l:=[];
%  while i<1 do
%  n:=1;for j from 1 to 10 do n:=n*(1+rand(10000)) od;
%  if is_pseudoprime(n+1)>0 then p:=n+1;i++; fi;
%  od;
%!s!
\squ Comment trouver la matrice des (facteurs,multiplicit\'es) d'un
entier. Comment effectuer une grande puissance en modulaire? 
%Divn:=transpose(ifactors(p-1)[2]);
%divn:=Divn[1];
%expn:=Divn[2];
%!s!<c>
%On cherche maintenant le certificat. Pour chaque premier divisant p-1 on trouve
%un element d'ordre la puissance maximale  de ce diviseur qui divise p-1. On
%utilisera factors et powmod
%!s!
%!s!<m>
%certifs:=[];
%for i in divn do
%a:=2;
%while powermod(a,(p-1)/i,p)=1 do a:=1+rand(p-1) od;
%certifs:=[op(certifs),a];
%od;
%!s!
\squ D\'eduire de votre certificat un g\'enerateur de $(\rela/p\rela)^\times$.
% g:=1;
% for i from 1 to dim(divn) do g:=mods(g*powmod(certifs[i],(p-1)/(divn[i]^expn[i]),p),p) od;
%# seq(powmod(g,i,p),i=divisors(p-1));# NON! trop de diviseurs!
\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 is_pseudoprime(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\'en\'erateur $g$
de $(\rela/n\rela)^\times$ lorsqu'il est cyclique. Trouver un
g\'en\'erateur $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\'eussi?
%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\'ecedemment.
% p:=l[3];
%g:=pari_znprimroot(p);
%#pari_znlog(3,Mod(g,p)); #depasse la memoire max de pari
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\exotitre{(reprise TP10)}
% !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...)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
% !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}

