Viquipèdia

Garbell sobre el cos de nombres generalitzat: diferència entre les revisions

Exploració interactiva de l'historial
← Edició anteriorEdició següent →
Contingut suprimit Contingut afegit
VisualWikitext
m Robot canvia 'seràn' per 'seran'
Correccions ortogràfiques.
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ó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 [[computació quàntica|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 garugrau ''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'' <sup>''n''</sup> 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''<sup>2</sup> + 1 i ''r'' és la unitat imaginària ''i'', llavors ''i''<sup>2</sup> + 1=0, o ''i'' <sup>2</sup> = −1. Això permet definir el producte complex:
:(''a''+''bi'')(''c''+''di'') = ''ac'' + (''ad''+''bc'')''i'' + (''bd'')''i''<sup>2</sup> = (''ac'' - ''bd'') + (''ad''+''bc'')''i''.
 
Obtingut de «https://ca.wikipedia.org/wiki/Garbell_sobre_el_cos_de_nombres_generalitzat»