Garbell sobre el cos de nombres generalitzat: diferència entre les revisions
Contingut suprimit Contingut afegit
Cap resum de modificació |
Cap resum de modificació |
||
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 — [[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
== Cos de nombres ==
| |||