Garbell sobre el cos de nombres generalitzat: diferència entre les revisions
Contingut suprimit Contingut afegit
Cap resum de modificació |
m Robot treu puntuació penjada després de referències |
||
Línia 3:
:<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>
(en notacions O i L notacions) per a una constant <math>c</math> que depèn de la mesura de complexitat i de la variant de l'algorisme.<ref>{{Ref-llibre|last = Pomerance|first = Carl|author-link = Carl Pomerance|date = December 1996|títol = A Tale of Two Sieves|periodical = Notices of the AMS|volume = 43|issue = 12|pages = 1473–1485|url = http://www.ams.org/notices/199612/pomerance.pdf|format = PDF}}</ref>
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.
Línia 33:
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.;<ref>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. [http://www.comlab.ox.ac.uk/oucl/work/richard.brent/pub/pub178.html] </ref>
Els millors resultats publicats<ref>{{cite | last=Franke |first=Jens |year=2006 |title=On RSA 200 and larger projects |url=http://www.hyperelliptic.org/tanja/SHARCS/talks06/Jens_Franke.pdf |format=PDF}}</ref>s'aconsegien pel mètode de [[Thorsten Kleinjung]].,<ref>{{cite journal | last=Kleinjung |first=Thorsten |year=2006 |month=October |title=On polynomial selection for the general number field sieve |journal=Mathematics of Computation |volume=75 |number=256 |pages=2037–2047 |url=http://www.ams.org/mcom/2006-75-256/S0025-5718-06-01870-9/S0025-5718-06-01870-9.pdf |format=PDF|accessdate=2007-12-13 |doi=10.1090/S0025-5718-06-01870-9}} </ref>
== Implementacions ==
| |||