Factorisation d’entiers¶
Les méthodes récentes de factorisation reposent sur le principe suivant : si \(n\) est divisible par \(p\), comment obtenir une congruence modulo \(p\) qui ne soit pas issue d’une congruence modulo \(n\) ?
Trois idées principales
utiliser le théorème d’Euler \(a^{p-1}=1\bmod p\) ;
tirer parti du hasard
construire patiemment des égalités entre carrés \(a^2=b^2\bmod n\).
Trial division et crible d’Eratosthène¶
Si \(n\) est composé, il existe \(p\leq\sqrt n\) qui divise \(n\). En testant la divisibilité par tous les entiers successifs on a un algorithme de factorisation naïf en \(O(\sqrt{n})\) divisions.
On peut améliorer légèrement en divisant par les seuls nombres premiers, soit via une base précalculée soit en effectuant un crible d’Eratosthène, ce qui ramène à \(O(\frac p{\log p})\) divisions pour trouver le facteur premier \(p\).
Méthode \(p-1\) de Pollard¶
Principe Si \(p\mid n\), alors pour tout \(a\) premier à \(n\) on a \(a^{p-1}=1\bmod p\). C’est aussi vrai si l’exposant est juste un multiple de \(p-1\) : si \(p-1\mid M\) alors \(p\mid \pgcd(a^M-1,n)\).
Or il est facile de trouver un tel multiple \(M\) si \(p-1\) n’a que des facteurs premiers assez petits.
Définition
Soient \(a\) et \(B\) deux entiers. On dit que \(a\) est \(B\)-friable si tous les facteurs premiers de \(a\) sont inférieurs à \(B\)
Proposition
Soit \(n\) un entier divisible par un facteur premier \(p\) tel que \(p-1\) soit \(B\)-friable. Alors en posant
on a pour tout \(a\in(\Z/n\Z)^\times\)
Concrètement, pour factoriser un entier \(n\), on procède en calculant de proche en proche les \(a^{M}\) pour \(M=M(B)\) croissant, jusqu’à ce que l’on obtienne les facteurs premiers de \(n\) les plus friables.
Exemple
Soient \(n=8051\), pour lequel on choisit de prendre \(a=2\) et une borne \(B=5\). On a
et on calcule successivement
Le facteur premier \(p=97\) sort lorsqu’on considère \(q=3\) : en effet, \(p-1=2^5\times 3\) est \(3\)-friable. Si l’on va jusqu’à \(B=5\), le facteur ne change pas, et en effet \(p=83\) est l’autre facteur premier de \(n\), pour lequel \(p-1=2\times 41\) n’est pas \(5\)-friable. Ce facteur ne sortira que pour \(B\geq 41\).
Proposition
Si \(n\) a un facteur premier \(p\) qui est \(B\)-friable, la méthode l’exhibe avec une complexité de
opérations binaires, où l’on note \(M(n)\) la complexité de la multiplication dans \(\Z/n\Z\).
pollard_p(n,B=10000,a=3) = {
aM = Mod(a,n);
forprime(p=2,B,
aM=aM^(p^logint(n,p));
g = gcd(lift(aM)-1,n);
if(g>1,break())
);
g;
}
Il est possible que tous les facteurs premiers de \(n\) aient même friabilité \(p-1\) (cf. \(M_{29}\) TP). Il n’est pas difficile d’adapter.
Une variante consiste à prendre un exposant de la forme \(M=B!\), qui est aussi multiple de beaucoup de nombres premiers.
pollard_p(n,B=10000,a=3) = gcd(lift(Mod(a,n)^B!-1),n);
Méthode \(\rho\) de Pollard¶
Principe On tire parti du phénomène statistique appelé paradoxe des anniversaires :
Proposition
Soit \(x_1,\dots x_k\) des éléments tirés selon une loi uniforme dans un ensemble de cardinal \(p\). Alors pour
la probabilité qu’ils soient tous disctincts est inférieure à \(1/2\).
Démonstration
La probabilité d’être distincts vaut
Si donc on tire des éléments \(x_i\) au hasard modulo \(n\), et si \(p\) est le plus petit facteur premier de \(n\), alors en \(O(\sqrt p)\) essais on aura \(x_i\equiv x_j\bmod p\) avec \(x_i\neq x_i\bmod n\), d’où le facteur \(p\mid\pgcd(x_i-x_j,n)\neq n\).
Toutefois, il est très coûteux de calculer les pgcd pour tout couple \(i,j\). Pour accélérer le procédé, l’idée de Pollard est de ne pas tirer des éléments aléatoires mais de les produire par la suite récurrente donnée par \(f:x\mapsto x^2+1\) ; pour \(x_0\in\Z/n\Z\), on pose \(x_{k}=f^k(x_0)\).
Il se trouve que cette suite se comporte de manière aléatoire, ou tout au moins conforme au paradoxe des anniversaire. D’autre part, le fait que l’itération soit polynomiale permet d’utiliser l’astuce suivante :
détection de cycle de Floyd
Soient \(f\in\Z[x]\), \(x_0\in\Z/n\Z\) et la suite récurrente \(x_k=f^k(x_0)\). Alors s’il existe \(i<j\) tel que \(x_i=x_j\bmod p\), il existe \(k<2j\) tel que \(x_k=x_{2k}\bmod p\).
Démonstration
Modulo \(p\), la suite est périodique de période \(j-i\) à partir du rang \(i\). Quitte à augmenter la période, on peut supposer \(j>2i\), alors \(k=j-i\) convient.
Remarque
Moralement cela revient à considérer un lièvre (\(x_{2k}\)) et une tortue (\(x_k\)) : à partir du moment où ils courent sur la même piste circulaire (la boucle du rho), il y a des moments où ils sont en même temps au même endroit. Il suffit de faire des pgcd à la suite des instants \(k\) (et non plus entre tout couple \(i,j\)).
Exemple
Avec \(n=8051\), on calcule les suites \(x_k\) et \(x_{2k}\), en les considérant d’emblée modulo \(p=97\).
\(k\) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
\(x_k\) |
1 |
2 |
5 |
26 |
95 |
5 |
26 |
95 |
5 |
\(x_{2k}\) |
1 |
5 |
95 |
26 |
5 |
95 |
26 |
||
\(\pgcd\) |
x |
1 |
x |
97 |
1 |
1 |
97 |
Proposition
Si l’on admet que la suite \(x_k\) a un comportement aléatoire, alors on trouve \(p\) en \(O(\sqrt{p})\) itérations, en particulier en \(O(\sqrt[4] n)\).
pollard_rho(n) = {
my(x,y,g);
x = y = g = 1;
while(g==1,
x = (x^2 + 1)
y = (y^2 + 1)
y = (y^2 + 1)
g = gcd(x-y,n);
);
g;
}
Remarque
Quand \(n\) est grand, on peut faire une petite amélioration du code précédent en remarquant qu’à chaque étape on calcule trois carrés et un pgcd modulo \(n\). Ce dernier est beaucoup plus coûteux, d’un facteur \(O(\log(n))\). L’amélioration consiste à accumuler un produit \(P=\prod(x_k-x_{2k})\bmod n\) sur \(L\) itérations \(k_0\leq k<k_0+L\), et à ne calculer qu’à ce moment \(\pgcd(P,n)\), en choisissant \(L\) de sorte que le coût du pgcd soit de l’ordre du coût des \(4L\) multiplications modulo \(n\) (3 carrés et un produit).
pollard_rho_acc(n,l) = {
my(x,y,g,p,l);
g = 1; if(!l,l = 1+logint(n,2)\30);
x = y = Mod(1,n);
while(g==1,
p = prod(i=1,l,
x = x^2 + 1;
y = y^2 + 1;
y = y^2 + 1;
x-y);
g = gcd(lift(p),n);
);
g;
}
Méthode de Fermat¶
Prenons à nouveau \(n=8051\). Fermat le factorise de tête en écrivant
Plus généralement, pour tout entier \(n\), on cherche un entier \(x>\sqrt{n}\) tel que le reste \(x^2\bmod n\) soit exactement un carré \(y^2\) de \(\Z\).
Cf. exercice .
En pratique, on peut aussi parcourir des nombres de la forme \(\floor{\sqrt{an}}+b\), pour \(a,b\geq 1\).
Méthodes de cribles algébriques¶
Partons d’un exemple plus retors, avec \(n=3239\). On a \(m=\floor{\sqrt{n}}=56\), et on calcule successivement
À ce stade, on n’a pas encore trouvé de carré. Toutefois, les trois relations multipliées entre elles forment la relation
qui permet de factoriser \(n\).
Exercice: de même, factoriser \(n=1649\), \(n=3247\).
L’idée de combiner plusieurs relations factorisées jusqu’à former un carré fonctionne de manière générale selon les principes suivants :
choisir une borne de friabilité \(B\), et numéroter \(p_1,\dots p_k\) les premiers inférieurs à \(B\)
parcourir les valeurs \(x^2-n\) pour \(\sqrt n < x < \sqrt{2n}\), à la recherche de relations \(B\)-friables
\[(x_i)^2 \equiv \prod_{j=1}^k p_j^{e_{i,j}} \bmod n\]que l’on mémorise
quand on a obtenu \(k+1\) telles relations, construire la matrice de parité des exposants du membre de droite
\[E = (e_{i,j})_{i,j} \bmod 2\]et déterminer un vecteur du noyau
\[\lambda \in \F_2^{k+1}, \lambda E=0.\]Ce vecteur indique quelles lignes selectionner de sorte que les exposants de la relation produit soient tous pairs, c’est-à-dire que l’on ait un carré à droite.
Calculer
\[\begin{aligned} x &= \prod_{i, \lambda_i=1} x_i \\ y &= \prod_{j=1}^k p_j^{\frac{\sum_{i, \lambda_i=1} e_{i,j}}2} \end{aligned}\]qui vérifient \(x^2\equiv y^2\bmod n\)
si \(x\not\equiv \pm y\bmod n\), \(\pgcd(x+y,n)\) est un facteur non trivial de \(n\).
Remarque
le choix de la borne de friabilité est délicat : si elle est trop petite, il y a peu de relations friables et l’on n’arrive pas à en trouver ; si elle est trop grande, il est plus facile de trouver des relations mais il faut en trouver beaucoup, et le temps mis à tester la friabilité est plus long.
la phase qui consiste à collecter des relations peut être l’objet de beaucoup d’améliorations : on peut partir de valeurs \(x_i\) aléatoires, de la forme \(\floor{\sqrt{an}}+y\equiv y^2+2m_ay+c_a\bmod n\), éliminer a priori de la base les premiers \(p\) tels que \(y^2+2m_ay+c_a\bmod p\) n’a pas de racine,…
on peut prendre plus de \(k+1\) relations, le noyau sera d’autant plus grand et cela permet de considérer d’autres vecteurs du noyau dans le cas où on aboutit à une relation triviale \(x\equiv\pm y\bmod n\).
il est utile de remarquer que certains premiers, en effet on connaît par avance les premiers \(p_i\) qui peuvent diviser \(x^2-n\) : ce sont ceux pour lesquels \(n\) est un carré modulo \(p_i\). De plus dans ce cas \(x\) doit être congru à l’une des deux racines carrées de \(n\) modulo \(p_i\).
une amélioration majeure est l’idée de crible : au lieu d’essayer de factoriser chaque valeur \(x^2-n\) par les premiers de la base en jetant toutes celles qui ne sont pas friables, on procède à l’envers : on fixe un intervalle de valeurs \(x\) à cribler, et pour chaque premier \(p\) de la base on ne divise par \(p\) que les valeurs \(x^2-n\) pour \(x\) congru aux racines \(x_1\) et \(x_2\) de \(x^2-n\) modulo \(p\) (que l’on connaît par avance). Les valeurs complètement factorisées après passage par tous les premiers de la base fournissent les relations.
le calcul d’un vecteur du noyau est une étape qui peut vite devenir délicate quand la taille de la base augmente : la matrice est de taille \(k^2\), avec \(k\) qui peut vite être de l’ordre du millier, et le calcul de \(\lambda\) est en \(O(k^3)\) opérations par la méthode de Gauss (réduction à une matrice triangulaire). Toutefois, en pratique la matrice \(E\) est creuse (la densité de coefficients non nuls est faible) et la méthode de Gauss a tendance à remplir la matrice. Il est préférable de stocker la matrice sous forme creuse (on ne mémorise que les emplacements de coefficients non nuls), et d’adopter des algorithmes de Wiedemann ou de Lanczos qui exploitent cette propriété.
avant de calculer le noyau, on peut simplifier la matrice en enlevant toutes les relations orphelines, c’est-à-dire des relations qui sont seules à faire intervenir un des facteurs de la base. On enlève aussi la colonne (nulle) correspondante.
d’autres améliorations : autoriser de relations avec un (ou deux) premiers hors de la base, remplacer les divisions lors de la phase de crible par une simple estimée de la taille du facteur friable (remplacer une division par une addition) pour deviner les bons candidats à la friabilité, utiliser sur le même intervalle de valeurs \(x\) plusieurs polynômes de la forme \(ax^2+bx+c\) avec \(n\mid b^2-4ac\), choisis pour prendre de petites valeurs…