\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}{11\baselineskip}
\topmargin=-5\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\everymath={\displaystyle}
\begin{document}
\noindent{\bf Universit\'e de Paris 7 \hfill \framebox{\Large \bf
    \hspace{ 1cm} TP7 \hspace{1cm}}\hfill   agreg 2007 (F.Han)}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
% interface(screenwidth=120);
\columnsep 0.7cm
\begin{multicols}{2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\exo Etudier la seconde partie du texte: exemple-Jury4 (m\'ethode de
Pollard)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \exo
 \qusqu Cr\'eer une proc\'edure \code{bete}, qui trouve le plus petit
diviseur de $n$ diff\'erent de $1$ et $2$, et qui retourne $n$ s'il n'y
en a pas, (en testant tous les nombres impairs de $3$ \`a
$\sqrt{n}$). Commentez cet algorithme par rapport au crible
d'Eratostene lorsque $n$ est grand.
% bete:=proc(n)
% i:=3;
% a:=0;
% while (i<evalf(sqrt(n))) 
%    do if (n mod i) <>0 then i:=i+2 
%       else a:=i;i:=n;
%       fi ; 
%    end do;
% if a<>0 then a; else n fi; 
% end proc; 
\squ Pour diff\'erentes valeurs de $a$ et $b$, tester \code{bete} sur
des nombres $N$ du type \code{nextprime(a)*nextprime(b)}. Donner un ordre de
grandeur sur le nombre de chiffres de $N$ pour que \code{bete} ne r\'eponde
plus.
\qu Si $n=pq$, o\`u $p$ et $q$ sont premiers, comment trouver $p$ si on
a trouv\'e $a$ et $b$ tels que $a=b [p]$ et $a\neq b [n]$?
\qu Cr\'eer une proc\'edure \code{pollard} qui \`a partir de $N$ trouve $i$ tel que
$(u_{2i}-u_i)\wedge N \neq  1$ o\`u $u_{i+1}=(u_i)^2+1[N]$, $u_0=1$.
\qusqu On pose:\\
\code{N:=nextprime(1000000)*nextprime(2000000);} tester
\code{pollard(N);} puis \code{bete(N);}
\squ Testez \code{pollard} pour plusieurs
valeurs de $N$ o\`u \code{bete} \'echoue.
% pollard := proc(n) 
% local x,y ; 
% x:=1; y:=x ; 
% while member ( igcd(y-x,n) , {1,n} ) do 
%      x:=x^2+1 mod n ; 
%      y:=(y^2+1)^2+1 mod n ; 
%      od ; 
% igcd(y-x,n); 
% end proc;

% N:=nextprime(10^8)*nextprime(2*10^8):pollard(N);
\qu Remarquer que si $u_i=u_j[p]$, alors $\forall s \geq 0,
u_{i+s}=u_{j+s}$, et donc que si $u_i=u_j[p]$ alors il existe $k$ tel
que $u_k=u_{2k}[p]$
\qusqu En modifiant \code{pollard}, faire une proc\'edure \code{comptep}
qui retourne une valeur 
flottante de $j\over \sqrt{p}$ o\`u $j$ est le nombre de tours effectu\'es par
pollard, et $p$ le diviseur trouv\'e par pollard.
\squ Etudier le
comportement de \code{comptep(N)} lorsque $N$ grandit. Conclure que Pollard
est en $O(\sqrt{p})$.
% #pollard est en O(sqrt(p)) ssi la fonction suivante est bornee.
% comptep:=proc(n)
% local x,y ;
% x:=1; y:=x ;j:=0;
% while member ( igcd(y-x,n) , {1,n} ) do
%      x:=x^2+1 mod n ;
%      y:=(y^2+1)^2+1 mod n ;
%      j:=j+1;od ;
% evalf(j/sqrt(igcd(y-x,n))); 
% end proc;
% l:=[];
% for i from 4 to 30 do
% N:=nextprime(rand(3^(i))())*nextprime(rand(2^(i+1))()):l:=[op(l),comptep(N)];
% end do:l;
\qusqu Quelle est la
probabilit\'e pour qu'un couple $(a,b)$ d'entiers inf\'erieurs \`a $n=pq$
soit tel que $a=b \mbox{ mod } n$? Celle pour que $a=b
\mbox{ mod } p$?
\squ On fait $i$ tirages  entre $0$ et $p$,  quelle est la probabilit\'e
pour  que 2  d'entre eux soient \'egaux?
\squ Cr\'eer la fonction:\\
\hfill\verb\P:=i->product(1-j/p,j=1..i-1);\. En
utilisant \code{limit} en \code{p=infinity}, montrer que $\log(P(2))$ est
\'equivalent \`a $-1/p$, $\log(P(3))\simeq -3/p$, $\log(P(4))\simeq
-6/p$.  Deviner une formule pour $\log(P(i))$ et testez la.
% P:=i->product(1-j/p,j=1..i-1);
% i:=2;limit(log(P(i))/(i*(i-1)/2/p),p=infinity);
% #On devine -i*(i-1)/(2p)
% l:=limit(log(P(2))/(i*(i-1)/2/p),p=infinity);
% for i from 3 to 50 do l:=l,limit(log(P(i))/(i*(i-1)/2/p),p=infinity) od:
% l;
%##########################################
\squ En utilisant cette formule, montrer que $P(i)>1/2$ d\`es que $i$
est de l'ordre de $1.18\sqrt{p}$
\qu Que se passe t'il si l'on prend comme fonction ``random'' du type
$u_{n+1}=a.u_n+c [n]$ au lieu de $(u_n)^2+1 [n]$?
% # u_2i=u_i est mauvais O(p) comme la methode bete
% # En effet u_2i=a^i u_i +c(a^i-1)/(a-1) [p], donc u_2i=u_i ssi
% # (a^i-1)(-ui+c/(a-1))=0[p]. Mais a^i=1[p] par ex si a generateur,
% # alors i>=p-1 
% 
% #illustration: on fait afficher rapport entre le nombre de tours et sqrt(p). 
% a:=54321123;c:=nextprime(10^4);
% comptelin:=proc(n)
% local x,y ;
% x:=1; y:=x ;j:=0;
% while member ( igcd(y-x,n) , {1,n} ) do
%      x:=a*x+c mod n ;
%      y:=a*(a*y+c)+c mod n ;
%      j:=j+1;od ;
% evalf(j/sqrt(igcd(y-x,n))); 
% end proc;
% l:=[];
%for i from 4 to 19 do
%N:=nextprime(rand(3^(i))())*nextprime(rand(2^(i+1))()):l:=[op(l),comptelin(N)];
%end do:l;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%% 
  \exo
  \qusqu Retrouver de quel paquet d\'epend la fonction
  \code{histogram}. Le charger.
% with(stats[statplots]);
  \squ Essayer \code{histogram([1,1,1,2,2]);} et
  \code{histogram([1,1,1,2,2],area=count);}. Quelle option faut il
  ajouter pour que l'on puisse voir sur l'histogramme le nombre de $1$
  et le nombre de $2$.
%histogram([1,1,1,2,2],area=count,numbars=2);
  \qu Essayer (manuellement) pour diff\'erentes valeurs de $n$,
  d'utiliser des histogrammes pour   \'etudier si \code{rand(n)} est une
  bonne fonction al\'eatoire uniforme.
  \qu Pour $n=2$, donner un ordre de grandeur sur le nombre de tirages
  pour que la   diff\'erence du nombre de $1$ et de $0$ ait l'air d'\^etre
  inf\'erieure \`a   $5\%$ sur votre histogramme.
% l:=seq(rand(2)(),i=1..100):
% histogram([l],area=count,numbars=2);  
% l:=seq(rand(2)(),i=1..1000):
% histogram([l],area=count,numbars=2);  
  \qusqu Prenons un nombre $N$ du type
  \verb\N:=nextprime(10^6)*nextprime(2*10^6);\. On consid\`ere
  la suite $u_{i+1}=(u_i)^2+1 \ [N]$.
  \squ Choisissez un $u_0$, et programmez $u$ par  r\'ecurence. Calculez
  $u(1)$, $u(2)$, $u(10000)$.
% u:=n->if n=0 then 2 else (u(n-1))^2+1 mod N fi; 
%# u(10000);Error, (in u) too many levels of recursion
% 
%
\squ Etudier la    r\'epartition des $(u_i)$
  modulo $N$ avec d'histogrammes. (Si n\'ec\'essaire, on pourra s'arranger pour que
  \code{histogramme} ne cr\'ee pas d'erreur du type ``floating point
  exception''). Peut on consid\'erer qu'ils sont    r\'epartis de mani\`ere
  uniforme?
% etudesuite := proc(n,M) 
% local x,l; 
% x:=12345;l:=[];
% for i from 1 to M do 
%      x:=x^2+1 mod n ; 
%      l:=[op(l),x];
%      od ; 
% l; 
% end proc;
% histogram(etudesuite(N,2000));
\newpage
\end{multicols}
\end{document}

