Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Factorisation de Dixon
Résumé
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.
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 et espérer que cela satisfait la congruence :
où 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
plusieurs valeurs de sont testées pour voir si se factorise complètement sur la base des facteurs. S'il le fait, la paire 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 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 est 30 870, nous avons :
Ceci donne un vecteur d'exposants de :
ou plus généralement :
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.