Méthode de factorisation de Dixon - Dixon's factorization method

En théorie des nombres , la méthode de factorisation de Dixon (également la méthode des carrés aléatoires de Dixon ou l'algorithme de Dixon ) est un algorithme de factorisation d'entiers à usage général ; c'est la méthode de base des facteurs prototypiques . Contrairement aux autres méthodes de base de facteurs, sa limite d'exécution est fournie avec une preuve rigoureuse qui ne repose pas sur des conjectures sur les propriétés de régularité des valeurs prises par polynôme.

L'algorithme a été conçu par John D. Dixon , mathématicien à l' Université Carleton , et a été publié en 1981.

Idée basique

La méthode de Dixon est basée sur la recherche d'une congruence de carrés modulo l'entier N qui est destiné à factoriser. La méthode de factorisation de Fermat trouve une telle congruence en sélectionnant des valeurs x aléatoires ou pseudo-aléatoires et en espérant que l'entier x ²  mod N est un carré parfait (dans les entiers):

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

Par exemple, si N = 84923 , (en commençant à 292, le premier nombre supérieur à √ N et en comptant) le 505 ² mod 84923 vaut 256, le carré de 16. Donc (505 - 16) (505 + 16) = 0 mod 84923 . Le calcul du plus grand commun diviseur de 505-16 et N en utilisant l'algorithme d'Euclide donne 163, ce qui est un facteur de N .

Dans la pratique, la sélection aléatoire x valeurs prendra un temps pour impractically trouver une congruence de carrés, car il n'y a que √ N carrés moins de N .

La méthode de Dixon remplace la condition "est le carré d'un entier" par la condition beaucoup plus faible "n'a que de petits facteurs premiers"; par exemple, il y a 292 carrés plus petits que 84923; 662 nombres inférieurs à 84923 dont les facteurs premiers ne sont que 2,3,5 ou 7; et 4767 dont les facteurs premiers sont tous inférieurs à 30. (Ces nombres sont appelés B-lisse par rapport à un certain B lié .)

S'il y a beaucoup de nombres dont les carrés peuvent être factorisés comme pour un ensemble fixe de petits nombres premiers, l'algèbre linéaire modulo 2 sur la matrice donnera un sous-ensemble des carrés dont les carrés se combinent en un produit de petits nombres premiers à une puissance paire - c'est-à-dire un sous-ensemble des carrés dont les carrés se multiplient en carré d'un nombre mod N (espérons-le différent). ${\ displaystyle a_ {1} \ ldots a_ {n}}$${\ displaystyle a_ {i} ^ {2} \ mod N = \ prod _ {j = 1} ^ {m} b_ {j} ^ {e_ {ij}}}$${\ displaystyle b_ {1} \ ldots b_ {m}}$${\ displaystyle e_ {ij}}$${\ displaystyle a_ {i}}$${\ displaystyle a_ {i}}$

Méthode

Supposons que le nombre composé N soit factorisé. Bound B est choisi, et la base de facteur est identifié (que l' on appelle P ), l'ensemble de tous les nombres premiers inférieur ou égal à B . Ensuite, des entiers positifs z sont recherchés tels que z ²  mod  N est B- lisse. Par conséquent, il peut être écrit, pour les exposants appropriés a _i ,

${\ displaystyle z ^ {2} {\ text {mod}} N = \ prod _ {p_ {i} \ in P} p_ {i} ^ {a_ {i}}}$

Quand suffisamment de ces relations ont été générées (il suffit généralement que le nombre de relations soit un peu plus que la taille de P ), les méthodes d' algèbre linéaire peuvent être utilisées (par exemple, élimination de Gauss ) pour multiplier ces différentes relations de telle manière que les exposants des nombres premiers du côté droit soient tous pairs:

${\ displaystyle {z_ {1} ^ {2} z_ {2} ^ {2} \ cdots z_ {k} ^ {2} \ equiv \ prod _ {p_ {i} \ in P} p_ {i} ^ { a_ {i, 1} + a_ {i, 2} + \ cdots + a_ {i, k}} \ {\ pmod {N}} \ quad ({\ text {où}} a_ {i, 1} + a_ {i, 2} + \ cdots + a_ {i, k} \ equiv 0 {\ pmod {2}})}}$

Cela donne une congruence de carrés de la forme a ² ≡ b ² (mod N ), qui peut être transformée en une factorisation de N , N = pgcd ( a + b , N ) × ( N / pgcd ( a + b , N )). Cette factorisation peut s'avérer triviale (c'est-à-dire N = N × 1 ), ce qui ne peut se produire que si a ≡ ± b (mod N ), auquel cas un autre essai doit être fait avec une combinaison différente de relations; mais une paire non triviale de facteurs de N peut être atteinte, et l'algorithme se terminera.

Pseudocode

input: positive integer ${\textstyle N}$
output: non-trivial factor of ${\textstyle N}$

Choose bound ${\textstyle B}$
Let ${\textstyle P:=\{p_{1},p_{2},\ldots ,p_{k}\}}$ be all primes ${\textstyle \leq B}$

repeat
    for ${\textstyle i=1}$ to ${\textstyle k+1}$ do
        Choose ${\textstyle 0<z_{i}<N}$ such that ${\textstyle z_{i}^{2}{\text{ mod }}N}$ is ${\textstyle B}$-smooth
        Let ${\textstyle a_{i}:=\{a_{i1},a_{i2},\ldots ,a_{ik}\}}$ such that ${\textstyle z_{i}^{2}{\text{ mod }}N=\prod _{p_{j}\in P}p_{j}^{a_{ij}}}$
    end for

    Find non-empty ${\textstyle T\subseteq \{1,2,\ldots ,k+1\}}$ such that ${\textstyle \sum _{i\in T}a_{i}\equiv {\vec {0}}{\pmod {2}}}$
    Let ${\textstyle x:=\left(\prod _{i\in T}z_{i}\right){\text{ mod }}N}$
        ${\textstyle y:=\left(\prod _{p_{j}\in P}p_{j}^{\left(\sum _{i\in T}a_{ij}\right)/2}\right){\text{ mod }}N}$
while ${\textstyle x\equiv \pm y{\pmod {N}}}$ 

return ${\textstyle \gcd(x+y,N)}$

Exemple

Cet exemple essaiera de factoriser N  = 84923 en utilisant la borne B  = 7. La base factorielle est alors P  = {2, 3, 5, 7}. Une recherche peut être faite pour les entiers entre et N dont les carrés mod N sont B- lisse . Supposons que deux des nombres trouvés soient 513 et 537: ${\ displaystyle \ left \ lceil {\ sqrt {84923}} \ right \ rceil = 292}$

${\ displaystyle 513 ^ {2} \ mod 84923 = 8400 = 2 ^ {4} \ cdot 3 \ cdot 5 ^ {2} \ cdot 7}$

${\ displaystyle 537 ^ {2} \ mod 84923 = 33600 = 2 ^ {6} \ cdot 3 \ cdot 5 ^ {2} \ cdot 7}$

Alors

${\ displaystyle (513 \ cdot 537) ^ {2} \ mod 84923 = 2 ^ {10} \ cdot 3 ^ {2} \ cdot 5 ^ {4} \ cdot 7 ^ {2} \ mod 84923}$

ensuite

${\ displaystyle {\ begin {aligné} & {} (513 \ cdot 537) ^ {2} \ mod 84923 \\ & = (275481) ^ {2} \ mod 84923 \\ & = (84923 \ cdot 3 + 20712 ) ^ {2} \ mod 84923 \\ & = (84923 \ cdot 3) ^ {2} +2 \ cdot (84923 \ cdot 3 \ cdot 20712) + 20712 ^ {2} \ mod 84923 \\ & = 0+ 0 + 20712 ^ {2} \ mod 84923 \ end {aligné}}}$

C'est, ${\ displaystyle 20712 ^ {2} \ mod 84923 = (2 ^ {5} \ cdot 3 \ cdot 5 ^ {2} \ cdot 7) ^ {2} \ mod 84923 = 16800 ^ {2} \ mod 84923.}$

La factorisation résultante est 84923 = pgcd (20712 - 16800, 84923) × pgcd (20712 + 16800, 84923) = 163 × 521.

Optimisations

Le tamis quadratique est une optimisation de la méthode de Dixon. Il sélectionne des valeurs de x proches de la racine carrée de N telles que x ² modulo N soit petit, augmentant ainsi largement les chances d'obtenir un nombre lisse.

D'autres moyens d'optimiser la méthode de Dixon incluent l'utilisation d'un meilleur algorithme pour résoudre l'équation matricielle, en tirant parti de la rareté de la matrice: un nombre z ne peut pas avoir plus de facteurs, de sorte que chaque ligne de la matrice est presque entièrement zéros. En pratique, l' algorithme de bloc de Lanczos est souvent utilisé. De plus, la taille de la base factorielle doit être choisie avec soin: si elle est trop petite, il sera difficile de trouver des nombres qui la factorisent complètement, et si elle est trop grande, il faudra collecter plus de relations. ${\ displaystyle \ log _ {2} z}$

Une analyse plus sophistiquée, utilisant l'approximation selon laquelle un nombre a tous ses facteurs premiers moins que la probabilité environ (une approximation de la fonction de Dickman – de Bruijn ), indique que choisir une base de facteurs trop petite est bien pire que trop grande, et que la taille de base de facteur idéale est une puissance de . ${\ displaystyle N ^ {1 / a}}$${\ displaystyle a ^ {- a}}$${\ displaystyle \ exp \ left ({\ sqrt {\ log N \ log \ log N}} \ right)}$

La complexité optimale de la méthode de Dixon est

${\ displaystyle O \ left (\ exp \ left (2 {\ sqrt {2}} {\ sqrt {\ log n \ log \ log n}} \ right) \ right)}$

en notation big-O , ou

${\ displaystyle L_ {n} [1 / 2,2 {\ sqrt {2}}]}$

en L-notation .

Références