Garbell sobre el cos de nombres generalitzat

En matemàtiques, el sedàs de cos de nombre general (GNFS) és l'algorisme clàssic més eficient conegut per factoritzar enters més grans de 100 dígits. Heurísticament, la seva complexitat per factoritzar un enter n (de log n bits) és de la forma

$O\left(e^{(c+o(1))(\log n)^{\frac {1}{3}}(\log \log n)^{\frac {2}{3}}}\right)=L_{n}\left[1/3,c\right]$

(en notacions O i L notacions) per a una constant $c$ que depèn de la mesura de complexitat i de la variant de l'algorisme. És una generalització del sedàs de cos de nombres especial: mentre que aquest últim només pot factoritzar nombres d'una certa forma especial, el sedàs de cos de nombres general pot factoritzar qualsevol nombre (a banda de potències de nombres primers, però això és un problema menor). Quan es fa servir el terme sedàs de cos de nombres (NFS) és sense qualificatiu, es refereix al sedàs de cos de nombres general.

El principi del sedàs de cos de nombre (tant especial com general) es pot entendre com a ampliació del sedàs racional més simple. Quan es fa servir el sedàs racional per factoritzar un nombre gran n, és necessari buscar nombres llisos (i.e. nombres amb factors primers petits) d'ordre n; la raresa d'aquests fan que el sedàs racional sigui poc pràctic. El sedàs de cos de nombre general, per altra banda, només exigeix una cerca de nombres llisos d'ordre n ^1/d , on d és algun enter més gran que u. Ja que els nombres més grans tenen moltes menys possibilitats de ser llissos que els nombres més petits, això és la clau a l'eficiència del sedàs de cos de nombres. Però per a aconseguir això augmentar la velocitat, el sedàs de cos de nombre ha de realitzar càlculs i factorizations en el cos de nombres. Això ocasiona molts aspectes bastant complicats de l'algorisme, en comparació amb el sedàs racional que és més simple.

Fixeu-vos que log n és el nombre de dígits en la representació binària de n, això és la mida de l'entrada a l'algorisme. En el (pitjor cas) el temps d'execució és superpolinomic respecte a la mida de l'entrada. És un problema obert important saber si la factorització es pot fer en termini prudencial — temps polinòmic — en un ordinador clàssic. En un ordinador quàntic, la factorització és un problema tractable que fa servir l'algorisme de Shor.

Cos de nombres

Suposant que f és un polinomi de grau n sobre Q (els nombres racionals), i r és una arrel complexa de f. Llavors f (r) = 0, que pot ser redistribuït per expressar r ⁿ com a combinació lineal de potències de r menors que n. Aquesta equació es pot fer servir per reduir algunes potènncies de r ≥ n. Per exemple, si f (x) = x² + 1 i r és la unitat imaginària i, llavors i² + 1=0, o i ² = −1. Això permet definir el producte complex:

(a+bi)(c+di) = ac + (ad+bc)i + (bd)i² = (ac - bd) + (ad+bc)i.

En general, això condueix directament al cos de nombres algebraics Q[r], que es pot definir com el conjunt de nombres reals donats per:

a_n-1r^n-1 + ... + a₁r¹ + a₀r⁰, on a₀,...,a_n-1 pertanyen a Q.

El producte de dos valors d'aquest tipus es pot calcular considerant el producte com polinomis, llavors reduint algunes potències de r ≥ n com s'ha descrit a dalt, produint un valor en la mateixa forma. Per assegurar que aquest cos sigui de fet n-dimensional i no col·lapsa a un cos ni tan sols més petit, és suficient que f sigui un polinomi irreductible. De manera similar, es pot definir l'anell de cos de nombres Z[r ] com el subconjunt de Q[r] on a₀...,a _n-1 es restringeixen a ser enters.

Mètode

S'escullen dos polinomis f (x) i g (x) de graus petits d i e, que tinguin coeficients enters, i que siguin irreductibles sobre els rationals, i que, quan s'interpreten mod N, tenen una arrel entera comuna m. No es coneix una estratègia òptima per escollir aquests polinomis; un mètode simple és triar un grau d per a un polinomi, considerar l'expansió de n en base M (acceptant dígits −m i m) per a un nombre de diferent m d'ordre n^1/d, i agafar f (x) com el polinomi amb els coeficients més petits i g (x) com x − m.

Es consideren els anells del cos de nombres Z[r ₁] i Z[r ₂], on r ₁ i r ₂ són arrels complexes dels polinomis f i g. Com que f és de grau d amb coeficients enters, si a i b són enters, llavors també ho serà b ^d·f (a /b), que s'anomena r. De forma similar s = b^e·g (a /b) és un enter. Es procura trobar valors enters de a i b que simultàniament facin que r i s tinguin facors primers petits respecte a la base escollida de nombres primers. Si a i b són petits, llavors r i s seran també petits, al voltant de la mida de m, i es tenen més probabilitats que siguin llisos alhora. L'aproximació més coneguda actual per a aquesta cerca és el tamisatge d'enreixat; per aconseguir rendiments acceptables, és necessari fer servirr una base de factor gran.

Tenint prou quantitat de parells d'aquests, fent servir el mètode de reducció de Gauss, es pot obtenir productes de cert r i del corresponent s que siguin quadrats alhora. Es necessita una condició una mica més dura, que siguin normes de quadrats en els nostres cossos de nombres, però es pot obtenir aquella condició per aquest mètode també. Cada r és una norma de a − r ₁b i per això es té que el producte dels factors corresponents a − r ₁b és una quadrat en Z[r ₁], amb una "arrel quadrada" que pot ser determinada (com a producte de factors coneguts en Z[r ₁])—; això es representa normalment com a nombre algebraic irracional. De manera similar, es té que el producte dels factors a − r ₂b és una quadrat en Z[r ₂], amb una "arrel quadrada" que també es pot calcular.

Com que m és una arrel dels dos f i g mod n, hi ha homomorfismes des dels anells Z[r ₁] i Z[r ₂] a l'anell Z/nZ (el mod N), que relaciona r ₁ i r ₂ amb m, i aquests homomorfismes faran correspondre cada "arrel quadrada" (típicament no representada com a nombre racional) al seu representant enter. Ara el producte dels factors a − mb mod n es pot obtinir com a quadrat en les dues bandes de l'homomorfisme. Així, es tenen dos nombres x i y, amb x ² − y ² divisible entre n i una altra vegada amb la probabilitat com a mínim 1/2 de tenir un factor de n trobant el màxim comú divisor de n i x − y.

Millorant l'elecció del polinomi

L'elecció de polinòmic pot afectar dramàticament el temps de completar la resta de l'algorisme. El mètode simple explicat abans d'escollir polinomis basat en l'expansió de n en base m és subòptim en moltes situacions pràctiques, això porta al desenvolupament de millors mètodes.

Un mètode d'aquests era suggerit per Murphy i Brent.; presenten un resultat dos parts per a polinomis, basat en la presència de d'arrels mòdul nombres primers petits i de valor mitjà que el polinomi pren sobre l'àrea de tamisatge.

Els millors resultats publicats s'aconseguien pel mètode de Thorsten Kleinjung., que permet g (x) = ax + b, i busca sobre a compost de factors primers petits congruent a 1 modulo 2d i sobre coeficients principals de f que són divisibles entre 60.

Implementacions

Fins a 2007, l'aplicació estàndard era una paquet de programari desenvolupat i distribuït per CWI als Països Baixos, que estava disponible només sota una llicència relativament restrictiva. El 2007, Jason Papadopoulos desenvolupava una aplicació més ràpida de processament final com a part de msieve, que és de domini públic. msieve, tanmateix, només pot córrer en un únic ordinador SMP, mentre l'aplicació de CWI es pot distribuir entre uns quants nusos en un grup amb connexions prou ràpides.

La selecció del polinomi es fa normalment pel programari de GPL escrit per Kleinjung, o per msieve, i el tamisatge d'enreixat per programari de GPL escrit per Franke i Kleinjung; aquests es distribueixen a GGNFS.

• NFSNet
• GGNFS.
• pGNFS
• factor by gnfs
• msieve, quin conté codi de processament final excel·lent, una bona aplicació de la selecció polinòmica que és molt bona per a nombres més petits, i una aplicació del sedàs de línia.
• kmGNFS

Referències

• Arjen K. Lenstra and H. W. Lenstra, Jr. (eds.). "The development of the number field sieve". Lecture Notes in Math. (1993) 1554. Springer-Verlag.l
• Richard Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective (2001). 2nd edition, Springer. ISBN 0-387-25282-7. Section 6.2: Number field sieve, pp. 278–301.l