t

[cours-maths-dis.git] / arithmetique / decomposition.tex

\section{Divisions successives}

L'algorithme est très simple : tenter de diviser le nombre par les nombres premiers successifs, dont on dispose dans un tableau.\\

Cet algorithme n'est pas efficace, mais il est nécessaire d'en disposer : tous les autres algorithmes, conçus pour trouver de \og grands\fg{} diviseurs, connaissent des cas d'échec, qui sont d'autant plus fréquents que les diviseurs sont petits.\\

Avant d'envoyer un nombre à un autre algorithme, il est donc indispensable de l'avoir débarrassé de ses \og petits\fg{} diviseurs. Pour fixer les idées, il s'agit des nombres premiers représentables sur 16 bits, jusqu'à 65 535 ($=2^{16}-1$) (le plus grand est 65 521, et il y en a au total 6 542).\\

Cette première phase de la décomposition nécessite en général un temps si faible qu'il n'est pas mesurable.

\begin{Rem}
On pourrait alors envisager aussi d'aller plus loin, c'est-à-dire, par exemple, de tenter la division par tous les nombres premiers représentables sur 32 bits (c'est-à-dire inférieurs à $2^{32}=4\,294\,967\,296$ : 10 chiffres \og seulement\fg{} !).

Il faut alors savoir qu'il y en a 203\,280\,221 et que la manière la plus économique de les stocker nécessite environ 194 Mo...\\

On n'ose évoquer le temps d'exécution d'un algorithme qui parcourrait un tel tableau\ldots pour ne même pas obtenir de résultat, ce qui est le cas dès que le plus petit diviseur du nombre à décomposer possède plus de 10 chiffres 'ce qui est fort peu pour des nombres qui dépassent les 100 chiffres décimaux).

Il faut bien saisir sur ces exemples l'ampleur du problème !
\end{Rem}



\section{Algorithme de Monte-Carlo (1975)}

\subsection{Présentation}

Cet algorithme, dont l'efficacité est tout-à-fait surprenante,
utilise un générateur de nombres au hasard (c'est de l'intervention de ce \og hasard\fg{} que l'algorithme tire son nom).\\


\noindent Soit
\begin{itemize}
 \item f cette fonction (le générateur),
\item $A$ la valeur d'initialisation,
\item $n$ le nombre à décomposer,
\item $p$ un de ses facteurs premiers.\\
\end{itemize}

On considère les suites de nombres entiers définies par $$x_0=y_0=A ,
 x_{m+1}=f(x_m) [n] ,  y_{m+1}=f(y_m) [p]$$

\begin{Rem}
On ne connaît pas $p$, bien sûr, mais on sait que $y_m=x_m [p]$, et cela suffit.
\end{Rem}


Soit h la plus grande puissance de 2 qui est inférieure ou égale à m (par exemple, pour $m=50, h=32$). On peut alors montrer qu'il existe un entier m tel que $y_m=y_{h-1}$, c'est-à-dire $x_m-x_{h-1} \equiv 0 [p]$.\\

C'est donc un multiple de p, qu'on pourra obtenir en calculant le PGCD de ce nombre avec n.

\subsection{L'algorithme}

L'algorithme peut se décrire dans les termes suivants :\\



{\prol
Initialisations : $n$ au nombre à factoriser
                  $x$ à 5, $x'$ à 2, $k$ à 1, $h$ à 1, $g$ à 1.\\

TANT QUE ($n$ n'est pas premier) ET QUE ($g$ est différent de $n$)
{\dec FAIRE
   {\dec REPETER
     {\dec g $\longleftarrow (x-x') \et n $
       SI ( $g$ est différent de 1) ALORS
       {\dec SI ( $g$ est différent de $n$) ALORS
         {\dec IMPRIMER $g$
            IMPRIMER \fg{} est un diviseur de\fg{} 
            IMPRIMER $n$
            $n \longleftarrow n / g $
            $x \longleftarrow x \% n$
            $x' \longleftarrow x' \% n$
         }
         FINSI
       }
       SINON 
       { \dec $k\longleftarrow k - 1$
         SI ( $k = 0 $) ALORS
         {\dec $x' \longleftarrow x$
           $h\longleftarrow 2h$
           $k \longleftarrow h$
         }
         FINSI
         $x\longleftarrow (x^2+1) \% n$
       }
       FINSI
   }
   JUSQU'A ($g$ est différent de 1)
  }
  FAIT
}
FIN
}

\bigskip

On notera que l'algorithme ainsi décrit, si l'on ne se trouve pas dans le cas d'erreur, \og tourne \fg{} tant qu'il n'a pas terminé la décomposition du nombre, ce qui peut durer très longtemps... Il faut, bien sûr, en plus, prévoir un arrêt au bout d'un certain temps.

\subsection{Discussion}

Même si, quelquefois, cet algorithme permet la factorisation de nombres plus grands, il ne peut pas prétendre arriver à décomposer tous les nombres de 20 chiffres ou moins.\\

Cette méthode est idéale pour les calculettes programmables.


\section{Algorithme du crible quadratique QS de Pomerance}

L'idée, dans cet algorithme comme dans de nombreux autres, et d'obtenir, si possible, des congruences de la forme $x^2\equiv y^2\ [n]$, $x$ n'étant ni congru à $y$, ni à $-y$. Dans ce cas, $(x-y)\et n$ sera un diviseur non trivial de $n$.

Ce qui distingue ces méthodes entre elles est la manière d'obtenir ces résidus quadratiques modulo $n$.\\

Ici, on prend les valeurs sur les entiers du polynôme $P(x)=(x+E(\sqrt n))^2-n$. Ces valeurs fournissent des congruences de la forme $y^2\equiv r\ [n]$, où $r$ est le résidu quadratique.\\

On peut repérer plus facilement ceux qui se factorisent aisément (par la méthode précédente, donc qui sont assez petits) en criblant les valeurs de $P(x)$ pour obtenir la congruence recherchée $x^2\equiv y^2\ [n]$ de manière efficace.\\


L'intérêt de cette méthode est qu'elle donne ses meilleurs résultats sur les nombres qui font échouer la suivante, mais elle est très difficile à programmer : le criblage n'est pas évident, et il y a énormément de \og petites astuces\fg{}, qui ne peuvent être examinées ici, pour retrouver les congruences recherchées aussi rapidement que possible.\\

C'est la méthode la plus utilisée avec celle, plus récente, des courbes elliptiques. On peut espérer décomposer des nombres jusqu'à 70 chiffres à peu près dans des temps raisonnables (on veut dire : quelques jours\ldots).

\section{Algorithme $(p-1)$ de Pollard}


Soit $p$ un diviseur premier du nombre $n$ à décomposer.\\


Si $a$ est premier avec $p$, $a^p \equiv a [p]$ (théorème de Fermat).

Comme $a$ est premier avec $p$, il est inversible modulo $p$, donc $a^{p-1} \equiv 1\ [p]$, soit $(a^{p-1}-1) \equiv 0\ [p]$, ou encore $(a^{p-1}-1)=kp$.

Donc $(a^{p-1}-1) \et n \neq 1$ : ce PGCD est donc un diviseur de $n$.\\

Le cas d'échec est celui où $k=0$, on trouve alors que le PGCD est $n$, et on n'obtient aucun renseignement sur un éventuel diviseur de $n$.\\

Par ailleurs, évidemment, on ne peut pas calculer $a^{p-1}$ quand on ne connaît pas $p$.\\

Il suffit en fait d'utiliser un multiple quelconque de $p-1$, soit $h(p-1)$.

On aura aussi $a^{h(p-1)} \equiv 1\ [p]$, il faudra donc utiliser comme exposant un nombre qui comporte le plus possible de facteurs premiers distincts, de manière à ce que les diviseurs de $p-1$ figurent tous dans la liste (c'est-à-dire que cet exposant soit de la forme $h(p-1)$)\\

Concrètement, on opère étape par étape, en utilisant le PPCM des entiers depuis 1 jusqu'à un maximum fixé.

\begin{Ex}
Soit à décomposer le nombre $n = R_{7}= 1\,111\,111 = 239 \times 4\,649$.

\begin{enumerate}
\item On doit choisir $a$, premier avec $p$, sans connaître $p$.

C'est facile, il suffit de choisir un nombre premier : s'il n'est pas égal à $p$, il est premier avec $p$. Par exemple : 2 (mais il vaut mieux prendre, en général, 3; il y a beaucoup plus de cas d'échec avec 2).\\

\item Le PPCM des entiers depuis 1 jusqu'à un maximum fixé
dans la recherche est égal à $2 \times 3 \times 2 \times 5
\times 7 \times 2 \times 3 \times 11 \times 13 \times 2 \times 17
\times 19 \times 23 \times 5 \times 3 \times 29 \times \ldots$

(Ces nombres figurent dans une table, déterminée à l'avance, et obtenue par l'algorithme suivant :
\begin{itemize}
\item On parcourt les entiers depuis 2 jusqu'au maximum fixé, tout en disposant de la table des nombres premiers inférieurs ou égaux à ce même maximum.
\item Chaque fois que l'on rencontre un nombre premier, on rajoute ce nombre premier.
\item Chaque fois que l'on rencontre une puissance d'un nombre premier, on rajoute un facteur égal à ce nombre premier, pour compléter le PPCM.
\end{itemize}
On obtient donc 2, puis 3, comme nombres  premiers, puis, en passant par 4, on rajoute un facteur 2, puis 5, premier, rien à rajouter pour 6, puis 7, premier, un facteur 2 supplémentaire en passant par 8, un facteur 3 à la rencontre de 9, etc\ldots

Cette table contient 6634 éléments pour le PPCM des entiers depuis 2 jusqu'à 65535, tous les nombres représentables sur 16 bits).\\

\item On effectue donc les calculs suivants 
\vspace{15pt}
\begin{center}\begin{tabular} {| c |c |c |c |c |c|} \hline
$a$ & $q$ & $a^q$ [n] & $a^q-1$ &  $(a^q-1)\et n$ & commentaire\\ 
\hline
2 & 2 & 4 & 3 & 1 & pas de diviseur \\
4 & 3 & 64 & 63 & 1 & pas de diviseur \\
64 & 2 & 4\,096 & 4\,095 & 1 & pas de diviseur\\
4\,096 & 5 & 120\,077 & 120\,076 & 1 & pas de diviseur\\
120\,077 & 7 & 1\,084\,896 & 1\,084\,895 & 1 & pas de diviseur\\
1\,084\,896 & 2 & 559\,627 & 559\,626 & 1 & pas de diviseur\\
559\,627 & 3 & 247\,053 & 247\,052 & 1 & pas de diviseur\\
247\,053 & 11 & 339\,352 & 339\,351 & 1 & pas de diviseur\\
339\,352 & 13 & 311\,394 & 311\,393 & 1 & pas de diviseur\\
311\,394 & 2 & 677\,377 & 677\,376 & 1 & pas de diviseur\\
677\,377 & 17 & 569\,060 & 569\,059 & 239 & diviseur trouvé...\\ \hline
\end{tabular}\end{center}
\vspace{15pt}
\item Explication : on a calculé en fait
$2^{2 \times 3 \times 2 \times 5 \times 7 \times 2 \times 3 \times 11 \times 13 \times 2 \times
17}=2^{24\,504\,480}$.

Or $24\,504\,480 = 102\,960 \times 238$, qui est bien de la forme $h(p-1)$ : le calcul de $a^{h(p-1)}$ a permis de trouver $p$.
\end{enumerate}
\end{Ex}



La capacité de cet algorithme à trouver un diviseur $p$ d'un nombre $n$ dépend de la taille du plus grand diviseur de $p-1$, ce qui explique ses résultats très inégaux.

\begin{Ex}
 Il trouve instantanément le diviseur
$p=1\,325\,815\,267\,337\,711\,173$ (19 chiffres décimaux) de $R_{53}$, parce que le plus grand diviseur premier de $p-1$ est $8\,941$.

Mais il ne peut pas obtenir le diviseur $q=106\,007\,173\,861\,643$
(15 chiffres décimaux seulement) de $R_{61}$, parce que le plus grand diviseur premier de $q-1$ est $868\,911\,261\,161$ (12 chiffres).
\end{Ex}



Ces considérations, dans l'optique du cryptage RSA, montrent que si l'on choisit deux nombres premiers $p$ et $q$ de la forme $p=2p'+1$ et $q=2q'+1$ où $p'$ et $q'$ sont eux-mêmes premiers (ce qui est assez facile à fabriquer), il suffira que $p'$ et $q'$ aient en gros au moins 12 chiffres pour que le cryptage soit invulnérable par l'algorithme de Pollard (mais pas par un autre algorithme, peut-être\ldots). 


\section{Algorithme de Lenstra (courbes elliptiques)}

\subsection{Introduction aux courbes elliptiques}

\begin{Def}[Courbe elliptique]
\index{courbe elliptique}
Une courbe elliptique sur un corps $K$ a une équation affine de la forme
$$y^2=x^3+ax+b$$

\noindent (en supposant que le discriminant $\Delta=4a^3+27b^2$ n'est pas nul, pour qu'elle ne soit pas dégénérée).
\end{Def}


\begin{Rem}
Elle a un point à l'infini dans la direction de $Oy$.
\end{Rem}


On considère deux points $P_1=(x_1,y_1)$ et $P_2=(x_2,y_2)$ d'une pareille courbe.\\


La droite $P_1P_2$ (la tangente en $P_1$ à la courbe dans le cas où $P_1=P_2$) recoupe la cubique en un troisième point de coordonnées
$(x_3,-y_3)$...

\begin{Def}
Si pose $P_3=(x_3,y_3)$ et $P_3=P_1+P_2$,
\begin{itemize}
 \item Cette addition sur la courbe elliptique est une loi de groupe abélien,
\item Elle est telle que l'élément neutre est le point à l'infini
\item ... et l'opposé du point $P=(x,y)$ est le point $P'=(x,-y)$.
\end{itemize}
\end{Def}


Les coordonnées de $P_3$ sont obtenues comme suit :

\bigskip

Si on pose 
$m=\left\{\begin{array}{l c l}
\fr{y_2-y_1}{x_2-x_1} & {\rm si} & P_1\neq P_2 \cr
\fr{3x_1^2+a}{2y_1} & {\rm si} & P_1=P_2 \cr
\end{array}\right.\ ,$ alors $\left\{\begin{array}{c c c}
x_3 & = & m^2-x_1-x_2 \cr
y_3 & = & m(x_1-x_3)-y_1 \cr
\end{array}\right.\ $.\par

\bigskip

\subsection{Algorithme de Lenstra}

Ici, il s'agit de calculer dans $\Z/n\Z$, qui n'est pas un corps, donc l'opération risque de ne pas être définie.

\begin{Rem}
C'est le cas lorsque $\delta=(x_2-x_1)\et n\neq 1$, auquel cas on ne peut poursuivre le calcul, car l'inverse de $(x_2-x_1)$ n'est pas défini.

Dans ce cas ($\delta\neq 1$), si $\delta\neq n$, on a trouvé un diviseur de $n$, et on a gagné. Si $\delta=n$, c'est le cas d'échec.
\end{Rem}




On applique la méthode de Pollard à la courbe elliptique, en calculant, à partir d'un point $P$ quelconque $P'=kP$, en cherchant les coefficients multiplicateurs dans le même tableau (celui des facteurs du PPCM évoqué plus haut). \\

Si l'on note $E(\Z/p\Z)$ le groupe additif de la courbe elliptique utilisée, l'intérêt d'opérer sur une courbe elliptique de cette sorte est que le cardinal de $E(\Z/p\Z)$ n'est pas nécessairement $p-1$ (comme dans la méthode classique $p-1$ exposée ci-dessus, où on travaille dans $(\Z/p\Z)^*$, de cardinal toujours $p-1$).


C'est un nombre de la forme $p+1-t$, où $|t|\infeg 2\sqrt p$, qui varie selon la courbe utilisée.\\


Ainsi, en travaillant sur plusieurs courbes simultanément, on augmente les chances que le plus grand diviseur de ce cardinal soit petit, ce qui conditionne, comme on l'a remarqué, le succès de la méthode.




\gsaut
\centerline{\x{Fin du Chapitre}}