Factorisation de Dixon

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 ${\displaystyle x}$ et espérer qu'elles satisfont à 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. 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.

Soit N le nombre à factoriser. On choisit un entier B (borne) et on calcule l'ensemble P = {p₁,..., 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² 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

${\displaystyle 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

${\displaystyle c_{1}a_{i1}+\cdots +c_{n+1}a_{i,n+1}=0\ \mathrm {mod} \ 2}$ pour ${\displaystyle 1\leq i\leq n}$.

Il s'agit de trouver une relation de dépendance linéaire entre les colonnes de la matrice ${\displaystyle (a_{ij}\ \mathrm {mod} \ 2)_{1\leq i\leq n,\ 1\leq j\leq n+1}}$ à coefficients dans le corps F₂ à deux éléments : l'algorithme du pivot de Gauss permet de le faire. On a alors :

${\displaystyle 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² = b² mod N, où ${\displaystyle a=\prod _{j\in T}z_{j}}$ et ${\displaystyle 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.