Ê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
Crible quadratique
Résumé
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éral des corps de nombres, lequel est cependant bien plus compliqué, et n'est plus performant que pour factoriser un nombre entier d'au moins cent chiffres. Le crible quadratique est un algorithme de factorisation non spécialisé, c'est-à-dire que son temps d'exécution dépend uniquement de la taille de l'entier à factoriser, et non de propriétés particulières de celui-ci.
L'algorithme, mis au point en 1981 par Carl Pomerance, est un raffinement de la méthode de factorisation de Dixon, elle-même basée sur celle de Fermat : on essaye d'établir une congruence de carrés modulo n (l'entier à factoriser), qui, souvent, conduit bien à une factorisation de n.
L'algorithme fonctionne en deux phases :
la phase de collecte des données, où il collecte les informations qui peuvent conduire à une congruence de carrés, et
la phase d'exploitation des données, où il place toutes les données qu'il a collectées dans une matrice et la résout pour obtenir une congruence de carrés.
La phase de collecte peut se paralléliser facilement et efficacement, mais pas la phase d'exploitation, à moins d'avoir peu de sous-systèmes et que chacun d'eux dispose d'une mémoire suffisante pour stocker toute la matrice (dans ce cas on peut utiliser l').
L'approche naïve pour trouver une congruence de carrés est de choisir un nombre au hasard, l'élever au carré, et espérer que le plus petit reste (positif ou nul) modulo n soit un carré parfait (i.e. soit le carré d'un entier). Par exemple, modulo 5959, l'entier 802 est congru à 441=212. Pour n grand, cette approche trouve rarement une congruence de carrés, mais lorsque cela arrive, cette congruence est le plus souvent non triviale donc permet de factoriser n.
La durée d'exécution du crible quadratique pour factoriser un entier n est en
avec la notation O de Landau et la notation L.
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.