Factorisation de Dixon

Un article de Wikipédia, l'encyclopédie libre.

Pour les articles homonymes, voir 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.

[modifier] Idée de base

La méthode de Dixon est basé sur la recherche d'une congruence de carrés. La méthode naïve de recherche d'une telle congruence est la sélection aléatoire de valeurs x et espérer que cela satisfait la congruence :

x^2\equiv y^2\quad(\hbox{mod }n),\qquad x\not\equiv\pm y.

où n est l'entier à factoriser. Dans la pratique, sélectionner aléatoirement les valeurs de x prendra un long temps impraticable pour trouver une congruence de carrés. La méthode de Dixon est basée sur la satisfaction d'une condition plus faible plusieurs fois, les résultats de ces valeurs peuvent être combinées en une congruence de carrés.

[modifier] Méthode

Premièrement, un ensemble de nombres premiers inférieurs à une certaine borne B est choisi. Cet ensemble de nombres premiers est appelé la base de facteurs. Alors, en utilisant le polynôme

p(x) = x2(mod n)

plusieurs valeurs de x sont testées pour voir si p(x) factorise complètement sur la base des facteurs. S'il le fait, la paire (x,p(x)) est stockée. Une telle paire est appelée une relation. Puis, une fois que le nombre de relations collectées dépasse la taille de la base de facteurs, nous pouvons entrer au niveau suivant.

Les valeurs p(x) sont factorisées (ceci est facile car nous sommes certains qu'ils factorisent complètement sur la base des facteurs) et les exposants des facteurs premiers sont convertis dans un vecteur d'exposant mod 2. Par exemple, si la base de facteurs est {2, 3, 5, 7} et la valeur de p(x) est 30 870, nous avons :

30 870=2^1\cdot3^2\cdot 5^1\cdot 7^3

Ceci donne un vecteur d'exposant de :

\mathbf{v}_i=\begin{bmatrix}1 \\ 2 \\ 1 \\ 3\end{bmatrix}=\begin{bmatrix}1 \\ 0 \\ 1 \\ 1\end{bmatrix}\hbox{ mod 2}

Si nous pouvons trouver une certaine manière pour ajouter ces vecteurs exposant ensemble (équivalent à la multiplication des relations correspondantes ensemble) pour produire le vecteur zéro (mod 2), alors nous pouvons obtenir une congruence de carrés. Ainsi nous pouvons placer les vecteurs exposant ensemble dans une matrice, et formuler une équation :

c_1\mathbf{v}_1+c_2\mathbf{v}_2+\cdots+c_n\mathbf{v}_n=\mathbf{0}\hbox{ (mod 2)}

Ceci peut être converti en une équation matricielle :

\begin{bmatrix} v_{11} & v_{12} & \cdots & v_{1n}\\ v_{21} & v_{22} & \cdots & v_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ v_{n1} & v_{n2} & \cdots & v_{nn} \end{bmatrix}\begin{bmatrix}c_1 \\ c_2 \\ \vdots \\ c_n\end{bmatrix}=\begin{bmatrix}0\\0\\ \vdots\\0\end{bmatrix}\hbox{ (mod 2)}

Cette équation matricielle est alors résolue (en utilisant, par exemple, l'élimination de Gauss) pour trouver le vecteur c. Alors :

\prod_{k}x_k^2\equiv\prod_{k}p(x_k)\pmod{n}

où les produits sont pris sur tous les k pour lesquels ck = 1. À cause de la manière utilisée pour la résolution de c, la partie droite de la congruence ci-dessus est un carré. Nous avons, alors, une congruence de carrés.

[modifier] Optimisations

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 factoriseront complètement sur elle. Si elle est trop grande, trop de relations devront être collectées.

Autres langues