Garbell sobre el cos de nombres generalitzat: diferència entre les revisions
Contingut suprimit Contingut afegit
m r2.6.5) (Robot afegeix: ru:Общий метод решета числового поля |
m Robot: Reemplaçament automàtic de text (- + ) |
||
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> É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).
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'', aixó és la mida de l'entrada a l'algorisme.
== Cos de nombres ==
Línia 19:
== Mètode ==
S'escullen dos [[polinomi]]s ''f'' (''x'') i ''g'' (''x'') de [[gau d'un polinomi|graus]] petits ''d'' i ''e'', que tinguin coeficients enters, i que siguin [[factorització dels polinomis|irreductibles]] sobre els [[nombre racional|rationals]], i que, quan s'interpreten [[aritmètica modular|mod ''N'']], tenen una [[arrel aritmètica|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 (àlgebra) |base]] ''M'' (acceptant dígits −''m'' i ''m'' ) per a un nombre de diferent ''m'' d'ordre ''n''<sup>1/''d''</sup>, i agafar ''f'' (''x'' ) com el polinomi amb els coeficients més petits i ''g'' (''x'') com ''x''
Es consideren els anells del cos de nombres '''Z'''[''r'' <sub>1</sub>] i '''Z'''[''r'' <sub>2</sub>], on ''r'' <sub>1</sub> i ''r'' <sub>2</sub> 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'' <sup>''d''</sup>·''f'' (''a'' /''b'' ), que s'anomena ''r'' . De forma similar ''s'' = ''b''<sup>''e''</sup>·''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é
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é.
Com que
== Millorant l'elecció del polinomi ==
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".
Els millors resultats publicats<ref>{{cita llibre | 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> que permet ''g'' (''x'' ) = ''ax''
== Implementacions ==
Fins a 2007, l'aplicació estàndard era una paquet de programari desenvolupat i distribuït per [[National Research Institute for Mathematics and Computer Science|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 part de msieve, que és de domini públic.
La selecció del polinomi és 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.
| |||