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é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.