Factorisation de Dixon

En arithmétique modulaire, la méthode de factorisation de Dixon (aussi connue comme l'algorithme de Dixon) est un algorithme de décomposition en produit de facteurs premiers à but général. Le crible quadratique est une modification de l'idée de base utilisée dans la méthode de Dixon. L'algorithme a été proposé par John D. Dixon, un mathématicien de l'université Carleton, et publié en 1981[1].

Idée de base

modifier

La méthode de Dixon est fondée sur la recherche d'une congruence de carrés. La méthode naïve de recherche d'une telle congruence consiste à choisir aléatoirement de valeurs et espérer qu'elles satisfont à la congruence :

est l'entier naturel à factoriser. En pratique, choisir aléatoirement les valeurs de x prend un long temps et s'avère impraticable pour trouver une congruence de carrés. La méthode de Dixon consiste à chercher plusieurs valeurs qui satisfont à une condition plus faible, puis à combiner les valeurs trouvées pour obtenir une congruence de carrés.

Méthode

modifier

Soit N le nombre à factoriser. On choisit un entier B (borne) et on calcule l'ensemble P = {p1,..., pn} des nombres premiers inférieurs ou égaux à B, ce qui forme la base de facteurs (en). On cherche ensuite des entiers z tels que z2 mod N soit B-friable, c'est-à-dire que ses facteurs premiers sont tous dans P. On peut dans ce cas trouver des exposants ai tels que

.

Lorsque l'on a trouvé assez de relations de ce genre – en général on cherche à en avoir n + 1 – ce qui donne des entiers zj et des exposants aij, on cherche des coefficients cj égaux à 0 ou 1 tels que

pour .

Il s'agit de trouver une relation de dépendance linéaire entre les colonnes de la matrice à coefficients dans le corps F2 à deux éléments : l'algorithme du pivot de Gauss permet de le faire. On a alors :

,

où tous les exposants du membre de droite sont pairs.

Cela donne une congruence de carrés a2 = b2 mod N, où et et T est l'ensemble des j tels que cj = 1. Cette congruence conduit à une factorisation de N, à savoir N = pgcd(a + b, N) × (N/pgcd(a + b, N)). Cette factorisation peut s'avérer triviale (i.e. N = N × 1), ce qui se produit exactement lorsque a = ±b mod N, auquel cas on peut réessayer avec une autre combinaison de relations. Si on trouve des facteurs non triviaux de N, l'algorithme s'arrête.

Optimisations

modifier

Le crible quadratique est une optimisation de la méthode de Dixon. Il résout une congruence quadratique pour trouver des valeurs de x plus rapidement qu'une simple sélection aléatoire.

D'autres manières pour optimiser la méthode de Dixon incluent l'usage d'un meilleur algorithme pour résoudre l'équation matricielle. En pratique, l'algorithme de Lanczos est souvent utilisé. Aussi, la taille de la base de facteurs doit être choisie avec précaution. Si elle est trop petite, il sera difficile de trouver les nombres qui se factoriseront complètement sur elle. Si elle est trop grande, trop de relations devront être collectées.

Notes et références

modifier
  1. John D. Dixon, « Asymptotically fast factorization of integers », Mathematics of Computation, vol. 36, no 153,‎ , p. 255-260 (DOI 10.1090/S0025-5718-1981-0595059-1, JSTOR 2007743).
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Dixon's factorization method » (voir la liste des auteurs).

Article lié

modifier