Factorisation de Dixon

La méthode de Dixon est basée 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 ${\displaystyle x}$ et espérer que cela satisfait la congruence :

${\displaystyle x^{2}\equiv y^{2}{\pmod {n}},\qquad x\not \equiv \pm y{\pmod {n}},}$

où ${\displaystyle n}$ est l'entier naturel à 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.

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

${\displaystyle p(x)\equiv x^{2}{\pmod {n}}}$

plusieurs valeurs de ${\displaystyle x}$ sont testées pour voir si ${\displaystyle p(x)}$ se factorise complètement sur la base des facteurs. S'il le fait, la paire ${\displaystyle (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 ${\displaystyle p(x)}$ sont factorisées (ceci est facile car nous sommes certains qu'ils se 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 ${\displaystyle p(x)}$ est 30 870, nous avons :

${\displaystyle 30870=2^{1}\cdot 3^{2}\cdot 5^{1}\cdot 7^{3}}$

Ceci donne un vecteur d'exposants de :

${\displaystyle \mathbf {v} _{i}={\begin{pmatrix}1\\2\\1\\3\end{pmatrix}}\equiv {\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}{\pmod {2}}}$

ou plus généralement :

${\displaystyle \mathbf {v} _{i}={\begin{pmatrix}v_{1i}\\v_{2i}\\\vdots \\v_{ni}\end{pmatrix}}}$

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

${\displaystyle c_{1}\mathbf {v} _{1}+c_{2}\mathbf {v} _{2}+\cdots +c_{n}\mathbf {v} _{n}\equiv \mathbf {0} {\pmod {2}}.}$

Ceci peut être converti en une équation matricielle :

${\displaystyle {\begin{pmatrix}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{pmatrix}}{\begin{pmatrix}c_{1}\\c_{2}\\\vdots \\c_{n}\end{pmatrix}}\equiv {\begin{pmatrix}0\\0\\\vdots \\0\end{pmatrix}}{\hbox{ (mod 2)}}}$

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

${\displaystyle \prod _{k}x_{k}^{2}\equiv \prod _{k}p(x_{k}){\pmod {n}}}$

où les produits sont pris sur tous les ${\displaystyle k}$ pour lesquels ${\displaystyle c_{k}=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.

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.

• Factorisation par fraction continue