\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} TP18 \hspace{1cm}}\hfill   agreg 2007 (F.Han)}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
%%\columnsep 0.7cm
%%\begin{multicols}{2}
% interface(screenwidth=120);
\def\code#1{{\tt #1}}
%% 
% interface(screenwidth=120);
\exotitre{Mini texte: Factorisation et fractions
  continues.\footnote{Ref: Koblitz: A course in number theory and Cryptography.}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Nous allons d{\'e}crire la m{\'e}thode utilis{\'e}e par d{\'e}faut par \code{ifactor}
pour factoriser un entier. Dans les ann{\'e}es 1960 Brillhart et Morrison
r{\'e}alisent \footnote{selon D.Knuth: The art of computer programming T2
  p396.} que la m{\'e}thode de Lehmer-Powers (Bull AMS 1931, et issue
d'id{\'e}es de Legendre et Kraitchik) m{\'e}rite d'{\^e}tre ressuscit{\'e}e {\`a} des fins
informatiques. 

L'id{\'e}e de d{\'e}part est la suivante: Si $b_1,...,b_k,n$ sont des entiers
naturels tels que   $n$ soit impair, on note
$a_i$,  un entier congru {\`a} $b_i^2$ modulo
$n$, dont la valeur absolue est major{\'e}e par $n/2$. On note alors
$p_1,...,p_N$ l'ensemble des diviseurs premiers de tous les $a_i$, et
$p_0=-1$, et l'on pose $\displaystyle a_i=\prod_{j=0}^N
p_j^{\alpha_{j,i}}$, (o{\`u} $\alpha_{j,i}$ peut {\^e}tre nul). On remarque
alors que si la matrice $(\alpha_{j,i})$ a
un noyau non nul dans $\rela/2\rela$, alors la donn{\'e}e d'un {\'e}l{\'e}ment non
trivial du noyau  et celle des $(p_i)$, permet
de construire   
une partie $I$ de $\{0\dots N\}$ et un {\'e}l{\'e}ment $c\in \rela$ tels que
$c^2=\prod_{i\in I} a_i$. On note alors $b=\prod_{i\in I} b_i\in\rela$, et
l'on remarque que si $b\neq \pm c [n]$, alors on a obtenu un diviseur
strict de $n$ en calculant $pgcd(b+c,n)$ et $pgcd(b-c,n)$. 

Pour utiliser ces remarques  lors d'une recherche d'un
diviseur non trivial d'un entier $n$, il faut trouver des $b_i$ tels
que les $a_i$  soient petits pour qu'ils se d{\'e}composent
rapidement, et/ou que les $(p_i)$ soient petits. De plus, pour $b\neq
\pm c [n]$ soit possible, il faut que  
$a_i\neq b_i^2$ dans $\rela$, ce qui est le cas si $b_i>\sqrt{n}$.

\bigskip On pourrait essayer cette m{\'e}thode en prenant des $b_i$
proches de $\sqrt{n}$. On am{\'e}liore maintenant le proc{\'e}d{\'e} en utilisant
des fractions continues.
%%
\def\pfraction#1#2{\frac{\mbox{$1$}}{#1+\mbox{$\frac{1}{#2}$}}}
\def\fraction#1#2#3#4{\pfraction{#1}{#2+\pfraction{\ddots}{#3+\frac{\mbox{$1$}}{#4}}}}
On note $[a_0,a_1,a_2,\dots,a_n]$ la fraction:
$$a_0+\fraction{a_1}{a_2}{a_{n-1}}{a_n}$$  
Lorsque $\xi=\xi_0$ un r{\'e}el non nul, on construit le d{\'e}veloppement en
fraction continue de $\xi=\xi_0$ par r{\'e}currence en notant $a_n$ la
partie enti{\`e}re de $\xi_n$, et 
en posant tant que $\xi_n$ n'est pas un entier:
$\xi_{n+1}=\frac{1}{\xi_n-a_n}$. On note $\frac{u_n}{v_n}$ la fraction
irr{\'e}ductible $[a_0,a_1,a_2,\dots,a_n]$. En fait, on pourrait montrer
que $u_n=a_n u_{n-1}+u_{n-2}$, $v_n=a_nv_{n-1}+v_{n-2}$ et
$u_{-2}=v_{-1}=0$ et $v_{-2}=u_{-1}=1$.
%#Calculer pour $n\in \nat$: $u_nv_{n-1}-u_{n-1}v_n$. Montrer que pour tout $\alpha$ on a
%#$[a_0,a_1,...,a_{n-1},\alpha]=\frac{\alpha u_{n-1}+u_{n-2}}{\alpha v_{n-1}+v_{n-2}}$ 
%# En d{\'e}duire lorsque les $a_n$ sont dans $\nat^*$ que \frac{u_n}{v_n}$ est
%# la fraction irr{\'e}ductible correspondant {\`a} $[a_0,a_1,\dots,a_n]$. 
De plus  si $\frac{u_k}{v_k}$ est une r{\'e}duite du d{\'e}veloppement
en fractions continues de $\sqrt{n}$, on a $|u_k^2-n
v_k^2|<2\sqrt{n}$, d'o{\`u} l'int{\'e}r{\^e}t de prendre pour les $b_i$ quelques
$u_i$.

\bigskip
\qu On pourra tenter d'illustrer sur un exemple cette m{\'e}thode de
factorisation.
\squ On pourra d'abord prendre  des $b_i$ de son choix proches de
$\sqrt{n}$ voire de $\sqrt{k.n}$, et un syst{\`e}me en $\alpha$ dont on
peut trouver une solution  de t{\^e}te.
\squ On pourra ensuite essayer d'automatiser ces {\'e}tapes.
\squ On pourra aussi prendre des $b_i$ calcul{\'e}s via des fractions continues.
\qu On pourrait aussi illustrer les affirmations sur les fractions continues.
\squ Par exemple illustrer graphiquement
$\frac{|u_k^2-nv_k^2|}{\sqrt{n}}$
\squ Ou calculer les $u_n,v_n$ avec les formules de r{\'e}curence et
v{\'e}rifier que $\frac{u_n}{v_n}$ est bien la fraction irr{\'e}ductible
$[a_0,a_1,a_2,\dots,a_n]$. 
% #On fait une proc{\'e}dure facteurs qui donne les facteurs d'un entier
% facteurs:=proc(n)
% l:=ifactors(n);
% {seq(i[1],i=l[2])};
% end proc;
%#on retourne un ensemble plutot qu'une liste pour ne pas repeter de facteurs.
% facteurs(123456789); {1,2} union {1,3};
% facteursliste:=proc(a)
% l:={};
% for i in a do l:=l union facteurs(i); od;
% end proc;
%# on aurait aussi pu utiliser factorset apres avoir fait with(numtheory);
% facteursliste([123456789,5*7,7*13]);#on teste
% #pour a utiliser mods et non modp. recherche d'une assez bonne liste pour n
% n:=nextprime(100)*nextprime(200);B:=floor(evalf(sqrt(n)))+1;
% #exemple a la main:
% for i from 0 to 6 do ifactor(mods((B+i)^2,n)); od; 
% #on voit  une relation entre i=0,1,5
% P:={-1,2,5,149};bb:=[B,B+1,B+5];
%a:=[seq(mods(bb[i]^2,n),i=1..3)];
% c:=P[2]*P[3]*P[4];b:=bb[1]*bb[2]*bb[3];
% igcd(c-b,n);#rate! on a b=c [n]
% # on peut aussi chercher autour de sqrt(k*n) 
% B:=floor(evalf(sqrt(3*n)))+1;
% for i from 0 to 6 do ifactor(mods((B+i)^2,n)); od; 
% #i=4 est un carre, c'est particulierement favorable.
% c:=sqrt(mods((B+4)^2,n));b:=B+4;igcd(c-b,n);#OK 211 divise n
% #un peu moins particulier:
% B:=floor(evalf(sqrt(4*n)))+1;
% for i from 0 to 6 do ifactor(mods((B+i)^2,n)); od; 
% #le produit des 2 premiers est un carre.
% c:=2*5*11;b:=B*(B+1);igcd(b-c,n);
% #On automatise ce que l'on vient de faire.
% a:={};b:={};for i from 1 to 10 do if max(op(facteurs(mods((B+i)^2,n))))<500
% then a:=a union {mods((B+i)^2,n)}; b:=b union {B+i}; fi; od;
% P:={-1} union facteursliste(a);P:=[op(P)];a:=[op(a)];b:=[op(b)];
% maxpow:=proc(p,n)
% nn:=n;k:=0;
% if p=-1 then k:=(1-sign(n))/2; fi;
% while (nn mod p = 0)and (p>1) do nn:=nn/p; k:=k+1; od; k; end proc;
% maxpow(5,5^3*7*2);
% alpha:=proc(a,P)
% Matrix([seq([seq(maxpow(pj,ai),pj=P)],ai=a)]);
% end proc;
% #Attention: il faut trouver la bonne instruction pour trouver un noyau mod 2
% with(LinearAlgebra):
% Nullspace(Matrix([[2]])) mod 2;
% A:=alpha(a,P);V:=(Nullspace(Transpose(A)) mod 2);
% c:=1;bb:=1; for i from 1 to nops(a) do if (V[1])[i]=1 then
% c:=c*a[i];bb:=bb*b[i]; fi ;od;c:=sqrt(c); igcd(bb-c,n);
% # on y incorpore des fractions continues. Attention a la precision:
% with(numtheory):
% cfrac(sqrt(n),7);
% #si l'on travaille avec 10 chiffres,...
% x:=evalf(sqrt(n),10):B:=floor(x):a:=[B]:
% for i from 1 to 7 do 
%  x:=evalf((1/(x-B),10)):B:=floor(x): 
%  a:=[op(a),B] od:a;#...le 7 ieme chiffre est deja faux.
% # On travaille avec 100 chiffres.
%  x:=evalf(sqrt(n),100);
%  a:={}:b:={}:uu:=0:u:=1:vv:=1:v:=0:B:=floor(x):
%#On remarque que  u*vv-v*uu vaut +/- 1
%  for i from 1 to 7 do
% oldu:=u:u:=B*u+uu:uu:=oldu:oldv:=v:v:=B*v+vv:vv:=oldv:
% a:=a union {mods((u)^2,n)}: b:=b union {u}:
% x:=evalf((1/(x-B),100)):B:=floor(x):print("u*vv-v*uu",u*vv-v*uu);
% od: evalf(u/v,100);#on verifie que ca tend vers racine  de n 
% P:={-1} union facteursliste(a):P:=[op(P)];a:=[op(a)];b:=[op(b)];
% A:=alpha(a,P);
%V:=(Nullspace(Transpose(A)) mod 2);
% c:=1;bb:=1;
% for i from 1 to nops(a) do if (V[1])[i]=1 then
% c:=c*a[i];bb:=bb*b[i]; print(c);fi ;od;
% c:=sqrt(c); igcd(bb-c,n);#pas de chance on a eu bb=c mod n
%#On essaye un n plus grand:
%n:=nextprime(1000)*nextprime(6000);
%  x:=evalf(sqrt(n),100);
%  a:=[]:b:=[]:uu:=0:u:=1:vv:=1:v:=0:B:=floor(x):
%  for i from 1 to 10 do
% oldu:=u:u:=B*u+uu:uu:=oldu:oldv:=v:v:=B*v+vv:vv:=oldv:
% a:=[op(a),mods((u)^2,n)]: b:=[op(b),u]:
% x:=evalf((1/(x-B),100)):B:=floor(x):
% od: evalf(u/v,100);#on verifie que ca tend vers racine  de n 
% P:={-1} union facteursliste({op(a)});P:=[op(P)];
% A:=alpha(a,P);
%V:=(Nullspace(Transpose(A)) mod 2);
% c:=1;bb:=1; for i from 1 to nops(a) do if V[1][i]=1 then
% c:=c*a[i];bb:=bb*b[i]; fi ;od;c:=sqrt(c); igcd(bb-c,n);
%

    
%%\newpage
%%\end{multicols}

\end{document}
