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

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 é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 k_i tels que r_i=k_i²-n factorise complètement sur un ensemble fixé (appelé base) de petits nombres premiers. Puis, en ayant suffisamment de tels r_i - 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 c_i égaux à 0 ou 1 tels que le produit de r_i^c_i soit un carré, disons x². D'un autre côté, si le produit de k_i^c_i est y, alors x²-y² 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 k_i fermé par la racine carrée de n - alors r_i est aussi de l'ordre de l'amplitude 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 l'extension de n dans la base m où m est d'ordre n^1/d. L'indication est d'obtenir des coefficients de f et g aussi petit 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] où r1 et r2 sont les racines des polynômes f et g, et examinons les valeurs a et b telles que r=b^d*f(a/b) et s=b^e*g(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 dans le 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 homomorphismes à partir des anneaux Z[r1] et Z[r2] vers l'anneau Z/nZ, qui appliquent r1 et r2 sur m, et ces homomorphismes 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-m*b mod n, nous pouvons obtenir un carré par deux manières - une pour chaque homomorphisme. Ainsi, nous avons deux nombres x et y, avec x²-y² 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.

Le meilleur algorithme connu jusqu'à présent pour la factorisation entière est l'Algorithme de Shor, qui factorise en temps polynomial. Il est dit non-classique car il se base sur la Mécanique quantique, et donc inutilisable pour les ordinateurs de cette génération.

Références

• Lenstra, Arjen K.; Lenstra, H.W. Jr. (Eds.) (1993). The development of the number field sieve. Lecture Notes in Math. 1554. Springer-Verlag.
• [PDF] Pomerance, Carl. A Tale of Two Sieves. Notices of the AMS 1996, 1473–1485.
• [PDF] Hazam, Khalid. Crible Généralisé sur le Corps de Nombres.

• Portail des mathématiques