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

Infos
En mathématiques, le crible général de corps de nombres est l'algorithme, fondé sur l'arithmétique modulaire, pour la décomposition en produit de facteurs premiers le plus efficace connu. Il utilise O\left\\exp\left\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 d
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 est l'algorithme, fondé sur l'arithmétique modulaire, pour la décomposition en produit de facteurs premiers le plus efficace connu. Il utilise O\left\\exp\left\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 coté, 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 fermé par la racine carrée de n - alors ri 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 mm est d'ordre n1/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 et Zr1 et r2 sont les racines des polynômes f et g, et examinons les valeurs a et b telles que r=bd
-f(a/b)
et s=b
-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 besoins 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, avec une « racine carrée » qui peut être déterminée (comme un produit de facteurs connus dans Z) - 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, 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 et Z 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 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 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

- Lenstra, Arjen K.; Lenstra, H.W. Jr. (Eds.) (1993). The development of the number field sieve. Lecture Notes in Math. 1554. Springer-Verlag.
- Pomerance, Carl. . Notices of the AMS 1996, 1473–1485. Catégorie:Algorithme de factorisation des entiers de:Zahlkörpersieb en:General number field sieve fi:Yleinen lukukuntaseula pl:GNFS zh:普通数域筛选法
Sujets connexes
Algorithmique   Anneau (mathématiques)   Arithmétique modulaire   Corps de nombres   Crible quadratique   Diviseur   Décomposition en produit de facteurs premiers   Factorisation en courbe elliptique de Lenstra   Mathématiques   Nombre premier   Norme (mathématiques)   Plus grand commun diviseur   Polynôme   Racine carrée  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^