Garbell sobre el cos de nombres generalitzat

De Viquipèdia
Dreceres ràpides: navegació, cerca

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. Heuristicament, 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.[1] É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[modifica | modifica el codi]

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 n com a combinació lineal de potències de r menors que n. Aquesta equació es pot fer servir per reduir algunes potènncies de rn. Per exemple, si f (x) = x2 + 1 i r és la unitat imaginària i, llavors i2 + 1=0, o i 2 = −1. Això permet definir el producte complex:

(a+bi)(c+di) = ac + (ad+bc)i + (bd)i2 = (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:

an-1rn-1 + ... + a1r1 + a0r0, on a0,...,an-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 rn 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 forma similar, es pot definir l'anell de cos de nombres Z[r ] com el subconjunt de Q[r] on a0...,a n-1 es restingueixen a ser enters.

Mètode[modifica | modifica el codi]

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 n1/d, i agafar f (x) com el polinomi amb els coeficients més petits i g (x) com xm.

Es consideren els anells del cos de nombres Z[r 1] i Z[r 2], on r 1 i r 2 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 = be·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 cosos de nombres, però es pot obtenir aquella condició per aquest mètode també. Cada r és una norma de ar 1b i per això es té que el producte dels factors corresponents ar 1b és una quadrat en Z[r 1], amb una "arrel quadrada" que pot ser determinada (com a producte de factors coneguts en Z[r 1])—; això es representa normalment com a nombre algebraic irracional. De forma similar, es té que el producte dels factors ar 2b és una quadrat en Z[r 2], 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 1] i Z[r 2] a l'anell Z/nZ (el mod N), que relaciona r 1 i r 2 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 amb mod n es pot obtinir com a quadrat en les dues bandes del homomorfisme. Així, es tenen dos nombres x i y, amb x 2y 2 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 xy.

Millorant l'elecció del polinomi[modifica | modifica el codi]

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.;[2] 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[3]s'aconsegien pel mètode de Thorsten Kleinjung.,[4] 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[modifica | modifica el codi]

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[modifica | modifica el codi]

  1. Plantilla:Copy book
  2. B. Murphy i R. P. Brent. "Sobre polinomis quadràtics per al sedàs de cos de nombres". Comunicacions d'Informàtica Australianes 20 (1998), pàg. 199–;213.
  3. Franke, Jens. On RSA 200 and larger projects (PDF), 2006. 
  4. Kleinjung, Thorsten. «On polynomial selection for the general number field sieve» (PDF). Mathematics of Computation, vol. 75, October 2006, pàg. 2037–2047. DOI: 10.1090/S0025-5718-06-01870-9 [Consulta: 13 desembre 2007].