Factorisation de Dixon

Factorisation de Dixon
Page d'aide sur l'homonymie 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.

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.

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.

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.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Factorisation de Dixon de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Factorisation De Dixon — 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… …   Wikipédia en Français

  • Factorisation de dixon — 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… …   Wikipédia en Français

  • Dixon — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.  Pour l’article homophone, voir Dickson. Sommaire 1 Patron …   Wikipédia en Français

  • Crible Quadratique — L algorithme crible quadratique (QS pour Quadratic sieve) est un algorithme moderne de décomposition en produit de facteurs premiers fondé sur l arithmétique modulaire. Dans la pratique, la seconde méthode connue la plus rapide. C est un… …   Wikipédia en Français

  • Crible quadratique — L algorithme du crible quadratique est un algorithme de factorisation fondé sur l arithmétique modulaire. C est en pratique le plus rapide après le crible généralisé sur les corps de nombres, lequel est cependant bien plus compliqué, et n est… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste Des Matières De La Théorie Des Nombres — Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 …   Wikipédia en Français

  • Liste des matieres de la theorie des nombres — Liste des matières de la théorie des nombres Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 …   Wikipédia en Français

  • Liste des matières de la théorie des nombres — Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 Test de primalité e …   Wikipédia en Français

  • Congruence de carrés — En arithmétique modulaire, une congruence de carrés modulo un entier n est une équation de la forme Utilisation Une telle équation apporte des informations utiles pour essayer de factoriser l entier n. En effet, Ceci veut dire que n divise le… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”