Metoda sită de câmp cu numere speciale

Metoda de sită a câmpurilor de numere speciale ( în engleză special number field sieve , SNFS) este o metodă de factorizare a numerelor întregi de un tip special. Din aceasta a fost derivată metoda sită a câmpului numeric general , care este cel mai eficient algoritm de factorizare pentru numere întregi mari . Metoda este eficientă pentru numere întregi de forma r e ± s , unde r N s Z, r și s sunt mici (de exemplu numere Mersenne ). $n>10^{{110}}$ $\în$ $\în$

Estimarea euristică a complexității factorizării numărului n este exprimată prin formula [1] :

e^{\left(1+o(1)\right)\left({\frac {32}{9}}\log n\right)^{\frac {1}{3}}\left (\log \log n\right)^{\frac {2}{3}}}=L_{n}\left[1/3,(32/9)^{1/3}\right]

Folosind SNFS, numărul Fermat care conține 155 de cifre zecimale [2] a fost factorizat . $F_{9}=2^{512}+1$

Origini

Ideea de bază a metodei a fost propusă pentru prima dată John Pollard articolul său [3] pe care l-a trimis colegilor săi în 1988. În acesta, și-a ilustrat metoda pe al șaptelea număr Fermat . Ideea a fost să se efectueze cernerea nu pe un inel de numere întregi, ca în metoda sităi pătratice , ci pe un câmp numeric algebric. În 1990, al nouălea număr Fermat a fost descompus folosind această metodă . Inițial, metoda era aplicabilă numai pentru numerele de formă specială 2 n ± c , motiv pentru care a fost numită „metoda cu sită de câmp de numere speciale”. Metoda a fost ulterior modificată pentru numere arbitrare și a numit metoda generală a sită numerică . $2^{128}+1$ $F_{9}=2^{512}+1$

Prezentare generală a metodei

SNFS se bazează pe metoda sită rațională mai simplă . Cititorul este încurajat să se familiarizeze cu această metodă înainte de a afla despre SNFS.

SNFS funcționează așa. Fie n numărul de factorizat. Similar cu metoda sită rațională, algoritmul SNFS poate fi împărțit în două etape:

Aflarea numărului de rapoarte multiplicative ale bazei factoriale Z / n Z mai mari decât numărul de elemente din baza factorilor.
Înmulțirea rapoartelor între ele în așa fel încât gradele produselor rezultate să fie aceleași, adică obținându-se rapoarte de forma a 2 ≡ b 2 ( mod n ). Aceasta, la rândul său, conduce la o factorizare a lui n : n = mcd ( a + b , n ) × mcd( a - b , n ). Dacă descompunerea obținută este trivială (adică n = n × 1), ar trebui să se caute alte produse ale relațiilor care îndeplinesc această condiție.

Al doilea pas este identic cu pasul din metoda sită rațională și este o problemă de algebră liniară . Spre deosebire de primul pas, care în această metodă este mai eficient.

Detalii metode

Fie n un număr factorizabil. Luați un polinom ireductibil f și un număr întreg m astfel încât f ( m ) ≡ 0 ( mod n ) (principiile de alegere a acestora vor fi explicate în secțiunea următoare). Fie α rădăcina lui f ; atunci există un inel Z [α]. Apoi există un inel de homomorfism φ între Z [ α ] și Z /n Z care mapează α la m . Pentru simplitate, presupunem că Z [ α ] este un inel factorial ; metoda poate fi modificată pentru cazul în care această condiție nu este îndeplinită, ceea ce va duce la calcule suplimentare.

Apoi creăm două baze de factori , una pentru Z [ α ] și una pentru Z. Baza factorului Z [ α ] conține toate numerele prime Z [ α ] a căror dimensiune este limitată de . Baza factorului Z , ca și în metoda sităi raționale, constă din numere prime până la un număr limită. $N_{\max )$

Apoi căutăm numere coprime ( a , b ) astfel încât:

a + bm este netedă în raport cu elementele bazei factorilor lui Z (adică toți divizorii săi primi sunt conținuti în baza factorilor).
a + bα este netedă față de elementele bazei factoriale Z [ α ]; din felul în care am ales elementele bazei factoriale, această condiție este echivalentă cu faptul că a + bα este divizibil doar prin numere prime mai mici decât . $N_{\max )$

Aceste perechi de numere se găsesc printr-o metodă de cernere asemănătoare cu sita lui Eratosthenes ; aceasta explică denumirea metodei sită câmp numeric.

Pentru fiecare astfel de pereche de numere ( a , b ) putem aplica inelul de homomorfism φ pentru a factoriza a + bα și inelul de homomorfism canonic de la Z la Z /n Z pentru a factoriza a + bm . Echivalându-le, obținem relații multiplicative pentru elementele bazei factorilor Z /n Z . După ce am găsit un număr suficient de astfel de rapoarte, le înmulțim între ele, așa cum este descris mai sus.

Alegerea opțiunilor

Nu orice număr este potrivit pentru factorizare prin metoda SNFS: este necesar să se găsească în prealabil un polinom f de un grad adecvat (se presupune că gradul optim este ; pentru numerele factorizabile la momentul dat, N este 4,5 sau 6) cu coeficienți mici și x astfel încât , unde N este numărul pentru factorizare . De asemenea, x trebuie să fie astfel încât să fie valabil pentru a și b nu mare . $\left(3{\frac {\log N}{\log \log N}}\right)^{1/3}$ $f(x)\equiv 0{\pmod {N)}$ $ax+b\equiv 0{\pmod {N}}$ $N^{1/d)$

Unul dintre tipurile de numere pentru care există astfel de polinoame sunt numerele de forma ; de exemplu, când NFSNET a descompus numărul 3^479+1, au folosit polinomul x^6+3 pentru x=3^80, deoarece (3^80)^6+3 = 3^480+3 și . $a^{b}\pm 1$ $3^{480}+3\equiv 0{\pmod {3^{479}+1))$

Numerele definite prin relații de recurență liniare, cum ar fi numerele Fibonacci și numerele Lucas , au și polinoame SNFS, dar sunt puțin mai dificil de obținut. De exemplu, are un polinom și o valoare x care satisface . [patru] $F_{709}$ $n^{5}+10n^{3}+10n^{2}+10n+3$ $F_{142}x-F_{141}=0$

Dacă cunoașteți câțiva divizori ai unui număr SNFS mare, puteți face calcule SNFS pentru restul; pentru exemplul de mai sus din NFSNET, 3^479+1 = (4 158071 7167757 7759574882776161031) ori un număr compus de 197 de cifre (divizorii mici au fost eliminați prin metoda ECM ), iar SNFS a fost aplicat pentru un număr de 197 cifre. Numărul de operații pentru NFS depinde de mărimea numărului original, dar unele calcule sunt mai rapide modulo un număr mai mic.

Restricții

Această metodă, după cum sa menționat mai sus, este foarte eficientă pentru numerele de forma r e ± s , unde r și s sunt relativ mici. Este eficient și pentru numerele care pot fi reprezentate ca un polinom cu coeficienți mici. Faptul este că metoda de sită specială a câmpurilor numerice cerne pentru două câmpuri numerice. Eficacitatea metodei depinde foarte mult de dimensiunea anumitor elemente din aceste domenii. Dacă un număr poate fi reprezentat ca un polinom cu coeficienți mici, numerele care sunt calculate sunt mult mai mici decât numerele cu care trebuie să se ocupe dacă un astfel de polinom nu există.

Vezi și

Metoda generală de sită a câmpului cu numere

Note

↑ Pomerance, Carl (decembrie 1996), A Tale of Two Sieves , Notices of the AMS vol . 43 (12): 1473–1485 , < http://www.ams.org/notices/199612/pomerance.pdf > Arhivat copie datată 11 noiembrie 2020 la Wayback Machine
↑ Vasilenko, O.N. (2003), Algoritmi de criptare teoretică a numărului , p. 93-107 , < http://www.ict.edu.ru/ft/002416/book.pdf > Arhivat 27 ianuarie 2007 la Wayback Machine
↑ Pollard, JM (1988), Factorizarea cu numere cubice
↑ Franke, Jens Note de instalare pentru ggnfs-lasieve4 . MIT Massachusetts Institute of Technology. Preluat la 4 decembrie 2011. Arhivat din original la 5 septembrie 2012. (nedefinit)

Literatură

Ișmukhametov, Sh.T. (2011), Metode de factorizare pentru numere naturale , p. 145-175 , < http://window.edu.ru/window_catalog/files/r73980/Monograph_ishm.pdf > (link nu este disponibil)
Byrnes, Steven (18 mai 2005), The Number Field Sieve , Math 129 , < http://modular.fas.harvard.edu/129-05/final_papers/Steve_Byrnes.pdf > . Extras 4 decembrie 2011. Arhivat 20 septembrie 2006 la Wayback Machine
Lenstra, A.K .; Lenstra, HW, Jr. ; Manasse, MS & Pollard, JM (1993), The Factorization of the Ninth Fermat Number , Mathematics of Computation vol. 61 (203): 319–349, doi : 10.1090/S0025-5718-1993-1182953-4 , < http: //www.std.org/~msm/common/f9paper.ps > Arhivat 4 februarie 2012 la Wayback Machine
Lenstra, A.K. & Lenstra, HW, Jr., eds. (1993), The Development of the Number Field Sieve , voi. 1554, Note de curs în matematică, New York: Springer-Verlag, ISBN 3540570136
Silverman, Robert D. (2007), Optimal Parameterization of SNFS, J. Mathematical Cryptology (de Gruyter) . — Vol. 1: 105–124

Link -uri

NFS@Home