Algorithme de factorisation par crible sur les corps de nombres généralisé

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, le crible général de corps de nombres, appelé aussi crible algébrique est l'algorithme, fondé sur l'arithmétique modulaire, pour la décomposition en produit de facteurs premiers le plus efficace des algorithmes classiques. Il utilise O\left\{\exp\left[\left({64\over9}\log n\right)^{1\over3} (\log \log n)^{2\over3}\right]\right\} étapes pour factoriser un nombre entier n (voir notation O). Il est dérivé du crible spécial de corps de nombres (SNFS). Lorsque la locution « crible de corps de nombres » est utilisée sans qualification, elle réfère au crible général de corps de nombres.

C'est une amélioration du crible quadratique, qui factorise n en trouvant les nombres ki tels que ri=ki2-n factorise complètement sur un ensemble fixé (appelé base) de petits nombres premiers. Puis, en ayant suffisamment de tels ri - qui sont appelés réguliers relativement à la base de facteurs choisie, en utilisant la méthode d'élimination de Gauss de l'algèbre linéaire nous pouvons choisir les exposants ci égaux à 0 ou 1 tels que le produit de rici soit un carré, disons x2. D'un autre côté, si le produit de kici est y, alors x2-y2 est divisible par n et avec la probabilité qu'au moins la moitié nous donne un facteur de n en trouvant le PGCD de n et x-y. Dans cette méthode, l'idée était de choisir ki proche de la racine carrée de n - alors ri est aussi de l'ordre de grandeur de la racine carrée de n et il existe suffisamment de valeurs régulières.

Le crible général de corps de nombres fonctionne de la manière suivante :

  • Nous choisissons deux polynômes irréductibles f(X) et g(X) avec une racine commune m mod n - on ignore quelle est la meilleure manière de choisir les polynômes, mais généralement cela se produit en prenant un degré d pour un polynôme et en considérant le développement de n en base mm est d'ordre n1/d. Le but est d'obtenir des coefficients de f et g aussi petits que possible - ils seront de l'ordre de m, tout en ayant les petits degrés d et e de nos polynômes.
  • Maintenant, nous considérons comme corps de nombres les anneaux Z[r1] et Z[r2]r1 et r2 sont les racines des polynômes f et g, et examinons les valeurs a et b telles que r = bdf(a/b) et s = beg(a/b) sont régulières relativement à la base de facteurs choisie. Si a et b sont petits, r et s le seront aussi (mais au moins de l'ordre de m), et nous avons une meilleure chance pour qu'ils soient réguliers en même temps.
  • En ayant suffisamment de paires, en utilisant la méthode d'élimination de Gauss, nous pouvons obtenir les produits de certains r et de son s correspondant pour qu'ils soient des carrés en même temps. Nous avons besoin d'une condition légèrement plus forte - qu'ils soient des normes de carrés dans notre corps de nombres, mais nous pouvons également obtenir cette condition par cette méthode. Chaque r est une norme de a- r1 b et donc, nous obtenons que ce produit de facteurs correspondants a- r1 b est un carré dans Z[r1], avec une « racine carrée » qui peut être déterminée (comme un produit de facteurs connus dans Z[r1]) - cela sera typiquement représenté comme un nombre algébrique irrationnel. De manière similaire, nous obtenons que ce produit de facteurs a- r2 b est un carré dans Z[r2], avec une « racine carrée » qui peut être aussi calculée.
  • Comme m est une racine et de f et de g mod n, il existe des morphismes des anneaux Z[r1] et Z[r2] vers l'anneau Z/nZ, qui appliquent r1 et r2 sur m, et ces morphismes appliqueront chaque « racine carrée » (typiquement non représentée comme un nombre rationnel) dans sa représentation d'entier. Maintenant, le produit de facteurs a-mb mod n, nous pouvons obtenir un carré par deux manières - une pour chaque homomorphisme. Ainsi, nous avons deux nombres x et y, avec x2-y2 divisible par n et de nouveau avec la probabilité qu'au moins dans une moitié, nous obtenons un facteur de n en trouvant le PGCD de n et x-y

Le deuxième meilleur algorithme classique, connu pour la factorisation entière est la méthode de factorisation en courbe elliptique de Lenstra. Il est meilleur que le crible général de corps de nombres lorsque les facteurs sont de petite taille, comme il fonctionne par recherche de valeurs régulières de l'ordre du plus petit diviseur premier de n, son temps d'exécution dépendant de la taille de ce diviseur.

Références[modifier | modifier le code]