\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}{14\baselineskip}
\topmargin=-5\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\everymath={\displaystyle}
\begin{document}
\noindent{\bf Universit\'e de Paris 7 \hfill \framebox{\Large \bf
    \hspace{ 1cm} TP13 M\'ethode de pollard \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
\exo
\qu Cr\'eer l'ensemble \verb/l:={1,4,5,6,7};/ et executez
\code{a:=rand(10):} Trouver une instruction permettant de savoir si $a$ est
dans l'ensemble $l$.
%l:={1,4,5,6,7};a:=rand(10):
%member(a,l);
%a; #verification.
\qu Attention \`a la priorit\'e de \code{mod}. Ex: \code{7+4 mod 3;}
%7 + 4 mod 3; (7+4)mod 3;
\qu Quel est le logarithme n\'ep\'erien? Quel est le nombre $e$. (Attention, en mode
maple le comportement est diff\'erent)
% maple_mode(1); # en mode maple
% ln(exp(1));ln(e);  #ca n'est que la lettre e, pas le reel.
% maple_mode(0);
% evalf(e); //la doc fait reference au mode xcas.
% maple_mode(1);
% evalf(exp(1));
% ln(exp(1));
% log(exp(1)); # les 2 marchent
%%\qu Comment obtenir un entier entre 0 et 20? Attention, que donne
%%\verb/rand(30^2);/ et \verb/rand(30^30);/
%%rand(30^2);rand(30^30); #il passe parfois en scientifique quand c'est trop grand?
\exo Etudier la seconde partie du texte: exemple-Jury4 (m\'ethode de
Pollard)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotitre{Exemples de d\'eveloppements}
\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}$)\footnote{Attention tout de m\^eme \`a ne pas calculer la racine carr\'ee \`a
chaque tour}. Commentez cet algorithme par rapport au crible
d'Eratostene lorsque $n$ est grand.
% !s!<c>
% bete comme le crible d'eratostene sont en O(p), et bete n'use pas de memoire.
% donc asymptotiquement, le crible n'est pas avantageux.
%!s!
% !s!<p>
% bete:=proc(n)
% i:=3;
% a:=0;
% SQ:=evalf(sqrt(n)); #pour ne le faire qu'une fois. ne pas le mettre dans le while!
% while (i<SQ) 
%    do if (n mod i) <>0 then i:=i+2; 
%       else a:=i;i:=n;
%       fi ; 
%    od;
% if a<>0 then a; else n fi; 
% end;
%!s!
\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.
%i:=4;N:=nextprime(10^i+5432)*nextprime(2*10^i+1234);
%bete(N);
%i:=5;N:=nextprime(10^i+5432)*nextprime(2*10^i+1234); #i=6 passe encore mais...
%bete(N);
\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 un diviseur
strict de $N$ en testant $(u_{2i}-u_i)\wedge N \notin  \{1,N\}$ o\`u
$u_{i+1}=(u_i)^2+1[N]$, $u_0=1$. (On remarquera que cette proc\'edure peut ne pas
aboutir.)
\qusqu tester \code{pollard(N);} avec:\\
\code{N:=nextprime(100000)*nextprime(200000);} 
\squ Testez \code{pollard} pour plusieurs valeurs de $N$ o\`u \code{bete} \'echoue.
% !s!<c>
% Attention, pour que  la suite r\'ecurrente soit bien programmee, il ne faut pas
% recalculer tous les termes jusque u_i ni u_2i a chaque etape!
%!s!
% !s!<p>
% 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;
%!s!
% N:=nextprime(10^6)*nextprime(2*10^6):
% pollard(N);
% N:=nextprime(10^8+5*rand(1000))*nextprime(2*10^8+11*rand(1000)):
% 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})$. On pourra cr\'eer une liste de valeurs, et dessiner cette liste.
%!s!<c>
% pollard est en O(sqrt(p)) ssi la fonction suivante est bornee.
%!s!<p>
% comptep:=proc(n)
% local x,y,j ;
% 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;
% !s!
% !s!<c>
%On cr\'ee une liste de valeurs. Il ne faut pas des nombres trop petits pour que
%pollard ait de bonne chance d'aboutir. On fait imprimer a chaque etape pour
%voir s'il blocque a une etape.
% !s!
% !s!<m>
% l:=[]; 
% for i from 7 to 30 do
% N:=nextprime((rand(3^(i))))*nextprime((rand(2^(i+1))));
% t:=comptep(N);
% print(i,t);
% l:=append(l,t);
% N:=nextprime((rand(3^(i))))*nextprime((rand(2^(i+1))));
% t:=comptep(N);
% print(i,t);
% l:=append(l,t);
% N:=nextprime((rand(3^(i))))*nextprime((rand(2^(i+1))));
% t:=comptep(N);
% print(i,t);
% l:=append(l,t);
% od;
%!s!
%plotlist(l); #ca a bien l'air borne
\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$? Expliquer pourquoi pollard boucle parfois pour des $n$ petits,
mais que l'on n'observe pas ce ph\'enom\`ene pour des nombres difficiles \`a factoriser. 
\squ On fait $i$ tirages  entre $0$ et $p$,  quelle est la probabilit\'e
pour  que 2  d'entre eux soient \'egaux? (Cf anniversaires)
\squ Cr\'eer la fonction:\\
\hfill\verb\P:=i->product(1-j/p,j=1..i-1);\. En
utilisant \code{limit} en \code{+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);
%!s!<c>
% On devine que P(i) equivaut a: -i*(i-1)/(2p), on l'illustre ainsi:
%!s!
% 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;
\squ En utilisant cette formule, montrer que $P(i)>1/2$ d\`es que $i$
est de l'ordre\footnote{C'est la borne du texte Jury4} de $1.18\sqrt{p}$ 
% !s!<c>
% Puisque ln est croissante, on se demande quand ln(P(i))>ln(0.5). On compare
% donc -ln(0.5) avec i^2/2p
%!s!
%sqrt(-2*ln(0.5)); #ca fait a peu pres le 1.18 de l'enonce  
\qu Que se passe t'il si l'on prend comme fonction ``random'' une suite du type
$u_{n+1}=a.u_n+c [n]$ au lieu de $(u_n)^2+1 [n]$?
%!s!<c>
%  u_2i=u_i est mauvais pour cette suite recurent, c'est en 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 
%!s! 
%!s!<c>
% illustration: on fait afficher le rapport entre le nombre de tours et sqrt(p). 
%!s!
% a:=54321123;c:=nextprime(10^4);
%!s!<p>
% 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;
%!s!
% l:=[];rand(3^4);
%!s!<m>
% for i from 4 to 19 do
% N:=nextprime(rand(3^i))*nextprime(rand(2^(i+1)));
% t:=comptelin(N);
%print(i,t);
%l:=append(l,t);
%od;
%!s!
%plotlist(l); # ca n'a plus l'air borne
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \exo
L'algorithme de pollard repose sur l'hypoth\`ese que les donn\'ees sont pioch\'ees de
mani\`ere al\'eatoire uniforme. Nous allons donc \'etudier ici si la suite r\'ecurrente
choisie a des statistiques coh\'erente avec cette hypoth\`ese.
\qu Etudier/r\'eviser les fonctions statistiques de votre logiciel. Par exemple
pour xcas: \code{histogram}, \code{classes}, \verb/diagramme_batons/
\qu Etudier un peu la r\'epartition des donn\'ees fournies par la fonction
\code{rand(2)}. Par exemple 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 sur votre
  histogramme d'\^etre   inf\'erieure \`a   $5\%$ du nombre de donn\'ees.
% l:=[seq(rand(2),i=1..100)]:
% histogram(classes(l,0,1)); #On commence a 0, largeur constante 1. 
% l:=[seq(rand(2),i=1..1000)]:
% histogram(classes(l,0,1));  
  \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\'ecurrence. Calculez
  $u(1)$, $u(2)$, $u(10000)$.
% N:=nextprime(10^6)*nextprime(2*10^6);
% u:=n->if n=0 then 2 else ((u(n-1))^2+1) mod N fi; 
% u(10); # u(10000);Error, (in u) too many levels of recursion
%
\squ Etudier la    r\'epartition des $(u_i)$   modulo $N$. (Cr\'eer une liste de
2000 termes). Attention, vu la taille
de $N$, on regroupera les donn\'ees en 40 classes, et l'on remarquera que le
diagramme en batons est plus appropri\'e que l'histogramme. Peut on consid\'erer
qu'ils sont    r\'epartis de mani\`ere   uniforme?
%!s!<m>
% 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;
%!s!
% donnees:=(etudesuite(N,2000));  
% cldonnees:=classes(donnees,0,N/40); #40 classes
% diagramme_batons(cldonnees); #on peut cacher les noms dans le menu Cfg
% !s!<c>
%-----------------Test d'une variante de pollard------------------------------------------
% cette variante de pollard pour minimiser le nombre de igcd n'apporte pas d'amalioration
% sous xcas, elle me semble meme un peu plus longue!!!!!!!
% !s!<p>
% pollard2 := proc(n) 
% local x,y,c,,yy,xx,pp ; 
% xx:=1; yy:=xx ;pp:=1;
% while member(igcd(pp,n), {1}) do
% x:=xx;y:=yy;
% for c from 1 to 20 do
%      xx:=(xx^2+1) mod n ; 
%      yy:=((yy^2+1)^2+1) mod n ; 
% pp:=(pp*(xx-yy)) mod n;
% od ; 
% od;
% while member ( igcd(y-x,n) , {1} ) do 
%      x:=(x^2+1) mod n ; 
%      y:=((y^2+1)^2+1) mod n ; 
%      od ; 
%      pp:=igcd(y-x,n);
% if (pp<>n) then pp else print("pas trouve") fi; 
% end proc:
% !s!
% N:=nextprime(10^6)*nextprime(2*10^6):
% pollard2(N);
% N:=nextprime(10^8+5*rand(1000))*nextprime(2*10^8+11*rand(1000)):
% pollard2(N);
% pollard(N);
\newpage
\end{multicols}

\end{document}

