Garbell sobre el cos de nombres generalitzat: diferència entre les revisions
Contingut suprimit Contingut afegit
Correccions ortogràfiques. |
m →Mètode |
||
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'' − ''m''.
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é petits, al voltant de la mida de ''m'', i es tenen més probabilitats que siguin llisos alhora. L'aproximació més coneguda actual per a aquesta cerca és el [[tamisatge d'enreixat]]; per aconseguir rendiments acceptables, és necessari fer servirr una base de factor gran.
| |||