4 \section{Divisions successives}
6 L'algorithme est très simple : tenter de diviser le nombre par les nombres premiers successifs, dont on dispose dans un tableau.\\
8 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.\\
10 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).\\
12 Cette première phase de la décomposition nécessite en général un temps si faible qu'il n'est pas mesurable.
15 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{} !).
17 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...\\
19 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).
21 Il faut bien saisir sur ces exemples l'ampleur du problème !
26 \section{Algorithme de Monte-Carlo (1975)}
28 \subsection{Présentation}
30 Cet algorithme, dont l'efficacité est tout-à-fait surprenante,
31 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).\\
36 \item f cette fonction (le générateur),
37 \item $A$ la valeur d'initialisation,
38 \item $n$ le nombre à décomposer,
39 \item $p$ un de ses facteurs premiers.\\
42 On considère les suites de nombres entiers définies par $$x_0=y_0=A ,
43 x_{m+1}=f(x_m) [n] , y_{m+1}=f(y_m) [p]$$
46 On ne connaît pas $p$, bien sûr, mais on sait que $y_m=x_m [p]$, et cela suffit.
50 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]$.\\
52 C'est donc un multiple de p, qu'on pourra obtenir en calculant le PGCD de ce nombre avec n.
54 \subsection{L'algorithme}
56 L'algorithme peut se décrire dans les termes suivants :\\
61 Initialisations : $n$ au nombre à factoriser
62 $x$ à 5, $x'$ à 2, $k$ à 1, $h$ à 1, $g$ à 1.\\
64 TANT QUE ($n$ n'est pas premier) ET QUE ($g$ est différent de $n$)
67 {\dec g $\longleftarrow (x-x') \et n $
68 SI ( $g$ est différent de 1) ALORS
69 {\dec SI ( $g$ est différent de $n$) ALORS
71 IMPRIMER \fg{} est un diviseur de\fg{}
73 $n \longleftarrow n / g $
74 $x \longleftarrow x \% n$
75 $x' \longleftarrow x' \% n$
80 { \dec $k\longleftarrow k - 1$
82 {\dec $x' \longleftarrow x$
87 $x\longleftarrow (x^2+1) \% n$
91 JUSQU'A ($g$ est différent de 1)
100 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.
102 \subsection{Discussion}
104 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.\\
106 Cette méthode est idéale pour les calculettes programmables.
109 \section{Algorithme du crible quadratique QS de Pomerance}
111 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$.
113 Ce qui distingue ces méthodes entre elles est la manière d'obtenir ces résidus quadratiques modulo $n$.\\
115 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.\\
117 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.\\
120 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.\\
122 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).
124 \section{Algorithme $(p-1)$ de Pollard}
127 Soit $p$ un diviseur premier du nombre $n$ à décomposer.\\
130 Si $a$ est premier avec $p$, $a^p \equiv a [p]$ (théorème de Fermat).
132 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$.
134 Donc $(a^{p-1}-1) \et n \neq 1$ : ce PGCD est donc un diviseur de $n$.\\
136 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$.\\
138 Par ailleurs, évidemment, on ne peut pas calculer $a^{p-1}$ quand on ne connaît pas $p$.\\
140 Il suffit en fait d'utiliser un multiple quelconque de $p-1$, soit $h(p-1)$.
142 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)$)\\
144 Concrètement, on opère étape par étape, en utilisant le PPCM des entiers depuis 1 jusqu'à un maximum fixé.
147 Soit à décomposer le nombre $n = R_{7}= 1\,111\,111 = 239 \times 4\,649$.
150 \item On doit choisir $a$, premier avec $p$, sans connaître $p$.
152 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).\\
154 \item Le PPCM des entiers depuis 1 jusqu'à un maximum fixé
155 dans la recherche est égal à $2 \times 3 \times 2 \times 5
156 \times 7 \times 2 \times 3 \times 11 \times 13 \times 2 \times 17
157 \times 19 \times 23 \times 5 \times 3 \times 29 \times \ldots$
159 (Ces nombres figurent dans une table, déterminée à l'avance, et obtenue par l'algorithme suivant :
161 \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.
162 \item Chaque fois que l'on rencontre un nombre premier, on rajoute ce nombre premier.
163 \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.
165 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
167 Cette table contient 6634 éléments pour le PPCM des entiers depuis 2 jusqu'à 65535, tous les nombres représentables sur 16 bits).\\
169 \item On effectue donc les calculs suivants
171 \begin{center}\begin{tabular} {| c |c |c |c |c |c|} \hline
172 $a$ & $q$ & $a^q$ [n] & $a^q-1$ & $(a^q-1)\et n$ & commentaire\\
174 2 & 2 & 4 & 3 & 1 & pas de diviseur \\
175 4 & 3 & 64 & 63 & 1 & pas de diviseur \\
176 64 & 2 & 4\,096 & 4\,095 & 1 & pas de diviseur\\
177 4\,096 & 5 & 120\,077 & 120\,076 & 1 & pas de diviseur\\
178 120\,077 & 7 & 1\,084\,896 & 1\,084\,895 & 1 & pas de diviseur\\
179 1\,084\,896 & 2 & 559\,627 & 559\,626 & 1 & pas de diviseur\\
180 559\,627 & 3 & 247\,053 & 247\,052 & 1 & pas de diviseur\\
181 247\,053 & 11 & 339\,352 & 339\,351 & 1 & pas de diviseur\\
182 339\,352 & 13 & 311\,394 & 311\,393 & 1 & pas de diviseur\\
183 311\,394 & 2 & 677\,377 & 677\,376 & 1 & pas de diviseur\\
184 677\,377 & 17 & 569\,060 & 569\,059 & 239 & diviseur trouvé...\\ \hline
185 \end{tabular}\end{center}
187 \item Explication : on a calculé en fait
188 $2^{2 \times 3 \times 2 \times 5 \times 7 \times 2 \times 3 \times 11 \times 13 \times 2 \times
189 17}=2^{24\,504\,480}$.
191 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$.
197 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.
200 Il trouve instantanément le diviseur
201 $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$.
203 Mais il ne peut pas obtenir le diviseur $q=106\,007\,173\,861\,643$
204 (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).
209 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).
212 \section{Algorithme de Lenstra (courbes elliptiques)}
214 \subsection{Introduction aux courbes elliptiques}
216 \begin{Def}[Courbe elliptique]
217 \index{courbe elliptique}
218 Une courbe elliptique sur un corps $K$ a une équation affine de la forme
221 \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).
226 Elle a un point à l'infini dans la direction de $Oy$.
230 On considère deux points $P_1=(x_1,y_1)$ et $P_2=(x_2,y_2)$ d'une pareille courbe.\\
233 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
237 Si pose $P_3=(x_3,y_3)$ et $P_3=P_1+P_2$,
239 \item Cette addition sur la courbe elliptique est une loi de groupe abélien,
240 \item Elle est telle que l'élément neutre est le point à l'infini
241 \item ... et l'opposé du point $P=(x,y)$ est le point $P'=(x,-y)$.
246 Les coordonnées de $P_3$ sont obtenues comme suit :
251 $m=\left\{\begin{array}{l c l}
252 \fr{y_2-y_1}{x_2-x_1} & {\rm si} & P_1\neq P_2 \cr
253 \fr{3x_1^2+a}{2y_1} & {\rm si} & P_1=P_2 \cr
254 \end{array}\right.\ ,$ alors $\left\{\begin{array}{c c c}
255 x_3 & = & m^2-x_1-x_2 \cr
256 y_3 & = & m(x_1-x_3)-y_1 \cr
257 \end{array}\right.\ $.\par
261 \subsection{Algorithme de Lenstra}
263 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.
266 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.
268 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.
274 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). \\
276 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$).
279 C'est un nombre de la forme $p+1-t$, où $|t|\infeg 2\sqrt p$, qui varie selon la courbe utilisée.\\
282 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.
288 \centerline{\x{Fin du Chapitre}}
