Garbell sobre el cos de nombres generalitzat: diferència entre les revisions
Contingut suprimit Contingut afegit
m Robot treu puntuació penjada després de referències |
m Robot treu enllaç igual al text enllaçat |
||
Línia 1:
En [[
:<math>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]</math>
Línia 7:
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 practic. El sedàs de cos de nombre general, per altra banda, només exigeix una cerca de nombres llisos d'ordre ''n'' <sup>1/''d'' </sup>, 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'', aisó é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 — [[
Línia 27:
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 [[norma d'una cos|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 ''a'' − ''r'' <sub>1</sub>''b'' i per això es té que el producte dels factors corresponents ''a'' − ''r'' <sub>1</sub>''b'' és una quadrat en '''Z'''[''r'' <sub>1</sub>], amb una "arrel quadrada" que pot ser determinada (com a producte de factors coneguts en '''Z'''[''r'' <sub>1</sub>])—; aixó es representa normalment com a [[nombre algebraic]] irracional. De forma similar, es té que el producte dels factors ''a'' − ''r'' <sub>2</sub>''b'' és una quadrat en '''Z'''[''r'' <sub>2</sub>], amb una "arrel quadrada" que també es pot calcular.
Com que ''m'' és una arrel dels dos ''f'' i ''g'' mod ''n'', hi ha [[homomorfisme]]s des dels anells '''Z'''[''r'' <sub>1</sub>] i '''Z'''[''r'' <sub>2</sub>] a l'anell '''Z/nZ''' (el [[Aritmètica modular|mod ''N'']] ), que relaciona ''r'' <sub>1</sub> i ''r'' <sub>2</sub> 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 del homomorfisme. Així, es tenen dos nombres ''x'' i ''y'', amb ''x'' <sup>2</sup> − ''y'' <sup>2</sup> divisible entre ''n'' i una altra vegada amb la probabilitat com a mínim 1/2 de tenir un factor de ''n'' trobant el [[
== Millorant l'elecció del polinomi ==
| |||