\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} TP08 M\'ethode de pollard \hspace{1cm}}\hfill   agreg 2013 (F.Han\footnote{http://www.math.jussieu.fr/$\sim$han/agreg})}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
\columnsep 0.7cm

% restart;maple_mode(0);cas_setup(0,0,0,1,0,1e-10,10,[1,50,0,25],0,0,0); //radians,pas de cmplx, pas de  Sqrt
%%\begin{multicols}{2}
%%\exo
%%\qu (En mode xcas) Cr\'eer l'ensemble \verb/l:=set[1,4,5,4,6,7];/ et executez
%%\code{a:=rand(10):;} Trouver une instruction permettant de savoir si $a$ est
%%dans l'ensemble $l$. Remarquez la diff\'erence avec une liste.
%%l:=%{1,4,5,6,7%};a:=rand(10):;
%%l:=set[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(2^30);/ et \verb/rand(2^31);/
%%rand(2^30);rand(2^31); //il passe parfois en scientifique quand c'est trop grand?

\bigskip
Nous allons \'etudier la seconde partie du texte: exemple-Jury4 (m\'ethode de
Pollard). Pour la premi\`ere partie vous pourrez regarder l'exemple dans l'aide
xcas: \verb/Exemples>crypto>rsa/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Th\`emes reli\'es:
\begin{itemize}
\item Fonction random ou variable al\'eatoire. Pertinence du mod\`ele choisi.
\item Suites r\'ecurrentes et applications.
\item Statistiques.
\item Factorisation, Complexit\'e.  
\end{itemize}
L'exercice suivant peut \^etre trait\'e sans avoir lu le texte, il permet de
d\'ecouvrir l'algorithme et de le tester. Vous pourrez lire ensuite le texte pour
avoir plus de d\'etails.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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(n):={
% j:=3;
% a:=0;
% SQ:=evalf(sqrt(n)); //pour ne le faire qu'une fois. ne pas le mettre dans le while!
% while (j<SQ) 
%    { if (irem(n,j)) <>0 then j:=j+2; 
%       else a:=j;j:=n;
%       fi ; 
%    };
% if a<>0 then a; else n fi; 
%};
%  !s!
\squ Comparez et commentez le temps d'execution de \verb/p:=nextprime(10**55)/
avec celui de \verb/isprime(p)/. 
\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.  Que fait nextprime? Attention, que fait \verb/rand(30)/ par rapport \`a
\verb/rand(2^43)/ dans certaines versions d'xcas? 
%j:=4;N:=nextprime(10^j+5432)*nextprime(2*10^j+1234);
%bete(N);
%j:=5;N:=nextprime(10^j+5432)*nextprime(2*10^j+1234); //j=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 programmera de mani\`ere efficace le calcul de
$u_{2i}$. On remarquera que cette proc\'edure peut ne pas
aboutir.)
\qusqu tester \code{pollard(N);} avec:
\verb/N:=nextprime(10^6)*nextprime(2*10^6);/ 
\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(n) :={ 
% local x,y ; 
% x:=1; y:=x^2+1; 
% while (member ( igcd(y-x,n) , set[1,n] ))
%    {
%      x:=irem((x^2+1), n) ; 
%      y:=irem((y^2+1)^2+1, n) ; 
%     }; 
% igcd(y-x,n); 
%};
%!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(n):={
% local x,y,j ;
% x:=1; y:=x^2+1 ;j:=0;
% while (member ( igcd(y-x,n) , %{1,n%} ))
%   {
%      x:=irem(x^2+1,n) ;
%      y:=irem((y^2+1)^2+1, n) ;
%      j:=j+1;
%   }
% evalf(j/sqrt(igcd(y-x,n))); 
% };
% !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.
%On met des floor pour les grands rand car avec certaines versions (anciennes) il bascule en flottant a partir de 2^31
% !s!
% !s!<m>
% l:=[]; 
% for(j:=7;j<31;j++){
% N:=nextprime(floor(rand(3^(j))))*nextprime(floor(rand(2^(j+1))));
% t:=comptep(N);
% print(j,t);
% l:=append(l,t);
% N:=nextprime(floor(rand(3^(j))))*nextprime(floor(rand(2^(j+1))));
% t:=comptep(N);
% print(j,t);
% l:=append(l,t);
% N:=nextprime(floor(rand(3^(j))))*nextprime(floor(rand(2^(j+1))));
% t:=comptep(N);
% print(j,t);
% l:=append(l,t);
% };
%!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:=i0->product(1-j/p,j=1..i0-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:=i0->product(1-j/p,j=1..i0-1);
% i0:=2;limit(log(P(i0))/(i0*(i0-1)/2/p),p,+infinity);
%!s!<c>
% On devine que P(i0) equivaut a: -i0*(i0-1)/(2p), on l'illustre ainsi:
%!s!
% l:=limit(log(P(2))/(i0*(i0-1)/2/p),p,+infinity);
% for i0 from 3 to 50 do l:=l,limit(log(P(i0))/(i0*(i0-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(i0))>ln(0.5). On compare
% donc -ln(0.5) avec i0^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(n,a,c):={
% local x,y ;
% x:=1; y:=irem(a*x+c, n) ;j:=0;
% while (member ( igcd(y-x,n) , %{1,n%} ))
%    {
%      x:=irem(a*x+c, n) ;
%      y:=irem((a*(a*y+c)+c) , n) ;
%      j:=j+1;
%    };
% evalf(j/sqrt(igcd(y-x,n))); 
% };
%!s!
% l:=[];rand(3^4);
%!s!<m>
% for(i0:=4;i0<20;i0++){ 
% N:=nextprime(rand(3^i0))*nextprime(rand(2^(i0+1)));
% t:=comptelin(N,a,c);
%print(i0,t);
%l:=append(l,t);
%};
%!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\'erentes avec cette hypoth\`ese.
\qu Etudier/r\'eviser l'utilisation des 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),j=1..100)]:;
% histogram(classes(l,0,1)); //On commence a 0, largeur constante 1. 
% l:=[seq(rand(2),j=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 irem(((u(n-1))^2+1) ,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. Comment ne pas
afficher les noms? Peut on consid\'erer
qu'ils sont    r\'epartis de mani\`ere   uniforme?
%!s!<m>
% etudesuite(n,M):={ 
% local x,l; 
% x:=12345;l:=[];
% for(i0:=1;i0<=M;i0++){
%      x:=irem((x^2+1), n) ; 
%      l:=[op(l),x];
%      }; 
% l; 
% };
%!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
\squ Etudier graphiquement les couples $(u_i\ [N],u_{2i}\ [N])$. (Cr\'eez une
fonction qui donne une liste de $M$ couples). Conclusion?
%!s!<m>
% etudesuite2(n,M):={ 
% local x,y,l; 
% x:=12345;l:=[];
% for(i0:=1;i0<=M;i0++){
%      x:=irem((x^2+1), n) ;
%      y:=irem((y^2+1)^2+1, n);
%      l:=[op(l),[x,y]];
%      }; 
% l; 
% };
%!s!
% couples:=(etudesuite2(N,200));  
% scatterplot(couples);
%!s!<c>
%l'hypothese d'independance semble raisonable.
%!s!


%!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(n) :={ 
% local x,y,c,yy,xx,pp ; 
% xx:=1; yy:=xx^2+1 ;pp:=1;
% while ((igcd(pp,n)==1))
%   { 
%    x:=xx;y:=yy;
%    for c from 1 to 20 do
%      xx:=irem((xx^2+1) , n) ; 
%      yy:=irem((yy^2+1)^2+1, n) ; 
%      pp:=irem(pp*(xx-yy) , n);
%    od ; 
%   }
%   while ( igcd(y-x,n)==1 )
%    {
%      x:=irem(x^2+1 , n) ; 
%      y:=irem((y^2+1)^2+1 , n) ; 
%    }  
%      pp:=igcd(y-x,n);
% if (pp<>n) then pp else print("pas trouve") fi; 
% }:;
% !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}

