# 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.

## Idée de base

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 $x$ et espérer qu'elles satisfont à la congruence :
    $x^{2}\equiv y^{2}{\pmod {n}},\qquad x\not \equiv \pm y{\pmod {n}},$
où $n$ 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

Soit N le nombre à factoriser. On choisit un entier B (borne) et on calcule l'ensemble P = {p$_1$,..., p$_n$} des nombres premiers inférieurs ou égaux à B, ce qui forme la base de facteurs (en). On cherche ensuite des entiers z tels que z$^2$ mod N soit B-friable, c'est-à-dire que ses facteurs premiers sont tous dans P. On peut dans ce cas trouver des exposants a$_i$ tels que
    $z^{2}\ \mathrm {mod} \ N=\prod _{i=1}^{n}p_{i}^{a_{i}}$.
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 z$_j$ et des exposants a$_{ij}$, on cherche des coefficients c$_j$ égaux à 0 ou 1 tels que
    $c_{1}a_{i1}+\cdots +c_{n+1}a_{i,n+1}=0\ \mathrm {mod} \ 2$ pour $1\leq i\leq n$.
Il s'agit de trouver une relation de dépendance linéaire entre les colonnes de la matrice $(a_{ij}\ \mathrm {mod} \ 2)_{1\leq i\leq n,\ 1\leq j\leq n+1}$ à coefficients dans le corps F$_2$ à deux éléments : l'algorithme du pivot de Gauss permet de le faire. On a alors :
    $z_{1}^{2c_{1}}z_{2}^{2c_{2}}\cdots z_{n+1}^{2c_{n+1}}=\prod _{i=1}^{n}p_{i}^{c_{1}a_{i1}+\cdots +c_{n+1}a_{i,n+1}}\ \mathrm {mod} \ N$,
où tous les exposants du membre de droite sont pairs.
Cela donne une congruence de carrés a$^2$ = b$^2$ mod N, où $a=\prod _{j\in T}z_{j}$ et $b=\prod _{i=1}^{n}p_{i}^{\sum _{j\in T}a_{ij}}$ et T est l'ensemble des j tels que c$_j$ = 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

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.