On a déjà étudié les méthodes de factorisation naïves et de Pollard (rho et p-1). On s’intéresse aux techniques de factorisation quadratiques.
Exemple : factoriser \(8051\) de cette manière.
En pratique, on peut effectuer deux améliorations :
Exemple: \(n=3239\), avec \(m=\floor{\sqrt{n}}=56\). On calcule les premières valeurs
À 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\).
Faire de même avec \(n=896641\) (factoriser les 15 premières valeurs).
On regarde les premières factorisations
n := 896641;
m := floor(sqrt(n));
for(x:=1;x<=15;x++) { print(ifactors(irem((m+x)^2,n)));}
On jette a priori toutes les relations qui ont des facteurs premiers \(>11\), il en reste \(6\).
En prenant les lignes \(3\), \(8\) et \(13\) on obtient une combinaison paire.
On généralise la technique de la manière suivante :
on considère une base de \(k\) facteurs premiers (auxquels on peut ajoute \(-1\)), \(B=\set{-1,2,3,5,7,\dots P}\) ;
on parcourt les valeurs \((\floor{\sqrt{n}}+b)^2\bmod n\) à la recherche de relations \(B\)-friables
que l’on mémorise
quand on a obtenu \(k+1\) telles relations, construire la matrice de parité des exposants du membre de droite
et déterminer un vecteur du noyau
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.
Ecrire une fonction premiers(k) qui renvoie la liste des \(k\) premiers
nombres premiers. Calculer P:=premiers(10).
premiers(k) := {
local j, P, p;
P := []; p := 1;
for(j:=1; j<=k; j++) {
p := nextprime(p);
P := append(P, p);
}
P;
}
Écrire une fonction friable(r,P) qui renvoie 0 si \(r\) n’est pas
produit des nombres de \(P\), et renvoie le vecteur des exposants sinon.
1 2 3 4 5 6 7 8 9 10 11 | friable(r, P) := {
local k,j,E,ej,p;
k := length(P);
E := [];
for(j:=0; j<k; j++) {
p := P[j]; ej:=0;
while(irem(r,p)==0) {r := iquo(r,p); ej++;}
E := append(E, ej);
}
if(r==1) { return(E); } else {return(0);}
}
|
Ecrire une fonction dixon(n,k,xmax) qui détermine une liste de \(k+1\) valeurs
\(x_i\) telles que les \(x_i^2\bmod n\) soient friables et la matrice \(E\)
des exposants \(e_{i,j}\) correspondants. La fonction pourra renvoyer une
matrice incomplète si moins de \(k+1\) valeurs friables ont été trouvées.
Plutôt que faire des appels à la fonction friable, on
remplit à chaque fois la matrice, en écrasant la ligne tant que la
relation n’est pas friable.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | dixon(n, k, xmax) := {
local E, m, r, P, j, l, x, X, p;
P := premiers(k);
E := newMat(k+1,k);
X := newList(k+1);
m := floor(sqrt(n));
l := 0;
for(x:=1; x<=xmax && l<=k; x++){
r := irem((m+x)^2 , n);
for(j:=0; j<k; j++) {
p := P[j]; E[l,j]:=0;
while(irem(r,p)==0) {r := iquo(r,p); E[l,j]:=E[l,j]+1;}
if(r==1) { X[l] := m+x; l++; break;}
}
}
return([E,X]);
}
|
Essayer la fonction avec \(n=557929\), et en déduire la factorisation de \(n\).
EX := dixon(557929,10,100):;
E:=EX[0]; X:=EX[1];
On trouve une factorisation via un vecteur du noyau modulo 2
K := ker(tran(E%2))%0
Examiner les matrices d’exposants obtenues. Que remarque-t-on ?
Deux choses principales :
Démontrer qu’une colonne correspondant à un nombre premier \(p\) ne peut avoir des coefficients non nuls que si \(n\) est un carré modulo \(p\).
on a un coefficient non nul en \(p\) si et seulement si \(p\) divise une valeur \((m+x)^2-n\), ce qui ne peut se produire que si \(n\equiv(x+m)^2\) est un carré modulo \(p\).
En déduire une modification de la fonction premiers qui améliore la
recherche de matrices de Dixon.
Ecrire une fonction factor_dixon(n,k,xmax) qui effectue la factorisation
avec la méthode de Dixon.
Note
On rappelle la méthode : si \(n\) possède un facteur premier \(p\) tel que \(p-1\) n’a que de petits facteurs premiers inférieurs à une borne \(B\) (on dit que \(p-1\) est \(B\)-friable), alors puisque \(a^{p-1}=1\bmod p\) on a également \(a^M=1\bmod p\) pour tout multiple \(M\) de \(p-1\), en particulier si l’on prend \(M\) égal à un produit de puissances de tous les petits nombres premiers inférieurs à \(B\).
Concrètement, on part d’un résidu \(a\) premier à \(n\), et pour chaque premier \(p_i\leq B\) on calcule un exposant \(b_i\) tel que \(p_i^{b_i}<n<p_i^{b_i+1}\). On pose \(M_i = M_{i-1}\times p_i^{b_i}\), et on calcule \(pgcd(a^{M_i}-1,n)\). Dès que l’on atteint la borne de friabilité d’un diviseur premier \(p\) de \(n\), \(p\) divise le pgcd.