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

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 7 decembrie 2019; verificările necesită 9 modificări .

Metoda generală a câmpului numeric ( în engleză general number field sieve , GNFS) este o metodă de factorizare pentru numere întregi . Este cel mai eficient algoritm de factorizare pentru numere mai lungi de 110 zecimale. Complexitatea algoritmului este estimată prin formula euristică [1]

\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\log n)^{\frac{1}{3}}(\log \log n)^{\frac{2}{3}}\right) =L_n\left[\frac{1}{3},\sqrt[3]{\frac{64}{9}}\right]

Metoda este o generalizare a metodei speciale a site-ului câmpului numeric: în timp ce aceasta din urmă permite doar factorizarea numerelor de un fel special, metoda generală funcționează pe mulțimea numerelor întregi, cu excepția puterilor primelor (care sunt factorizate trivial prin prinzând rădăcini).

Istorie

În 1988, matematicianul englez John Pollard a descris o nouă metodă de factorizare a numerelor întregi de o formă specială ( ), ilustrând-o cu extinderea celui de-al șaptelea număr Fermat . Spre deosebire de metoda sităi pătratice , în care cernerea se efectuează pe inelul tuturor numerelor întregi, metoda propunea folosirea inelului de numere întregi peste un câmp numeric . Manuscrisul a fost anexat cu o scrisoare adresată lui Andrew Odlyzko , iar Richard Brent , John Brillhart , Hendrik Lenstra , Klaus Schnorr și H. Suyama au primit de asemenea copii . În această scrisoare, Pollard a sugerat că poate această metodă ar putea fi folosită pentru a extinde al nouălea număr Fermat . [2] $2^n \pm C$ $F_7 = 2^{128}+1$ $Z([2^{3/2}])$ $Î(2^{3/2})$

În 1990, A. Lenstra , H. Lenstra, Mark Manasse și Pollard au descris prima implementare pe scară largă a noii metode, cu unele îmbunătățiri. Ei au arătat că algoritmul funcționează mai rapid pe numere de tip special decât toate celelalte metode de factorizare cunoscute. Lucrarea discută, de asemenea, ideea lui Joe Buhler și Karl Pomerans de a îmbunătăți metoda de descompunere a oricăror numere întregi și prezintă soluția la această problemă. [3]

Mai târziu , Leonard Max Adleman a propus utilizarea caracterului pătratic pentru a găsi pătrate într-un câmp numeric. Aceasta a oferit o soluție alternativă la problema ridicată de Buchler și Pomerance și a îmbunătățit timpul de funcționare estimat al site-ului de câmp numeric atunci când este aplicat numerelor de tip nespecial. [patru]

În același an, A. Lenstra, H. Lenstra, Manasse și Pollard au prezentat extinderea celui de-al nouălea număr Fermat folosind metoda câmpului numeric. În lucrarea corespunzătoare, sunt discutate multe detalii despre această descompunere. [5]

În cele din urmă, în „Factorizarea numerelor întregi cu sită de câmp numeric”, Buchler, H. Lenstra și Pomerance au descris metoda sită a câmpului numeric ca fiind aplicată numerelor care nu au neapărat o formă specială. [6] Această implementare a algoritmului a inclus un pas care implică calcule folosind numere extrem de mari. Jean-Marc Kuwaignes în lucrarea sa a descris o modalitate de a ocoli acest lucru. [7]

Rezultatele dezvoltării timpurii a metodei au fost rezumate de o colecție de articole editate de A. Lenstra și H. Lenstra. [8] Printre altele, colecția a inclus un articol de Bernstein și A. Lenstra, care descrie o altă implementare îmbunătățită a algoritmului. Articolul a fost inclus în colecția la rubrica „Metoda generală a sitei câmpului numeric”. [9]

Esența metodei

Metoda sită câmp numeric (atât specială, cât și generală) poate fi gândită ca o îmbunătățire a unei metode mai simple, metoda sită rațională sau metoda sită pătratică. Algoritmii asemănători lor necesită găsirea unor numere netede de ordine . Mărimea acestor numere crește exponențial cu . Metoda sită a câmpului numeric, la rândul său, necesită găsirea numerelor netede care sunt subexponențiale în raport cu dimensiunea. Deoarece aceste numere sunt mai mici, este mai probabil ca un număr de această dimensiune să fie neted, motiv pentru care metoda sită a câmpului numeric este atât de eficientă. Pentru a obține accelerarea calculelor în cadrul metodei, acestea sunt efectuate în câmpuri numerice , ceea ce complică algoritmul, în comparație cu o sită rațională mai simplă. ${\sqrt {n}}$ $n$ $n$

Principii de bază

Metoda de factorizare a lui Fermat pentru factorizarea numerelor impare naturale n , constând în găsirea numerelor întregi x și y astfel încât , ceea ce duce la o factorizare a . $x^{2}-y^{2}=n$ $n=(xy)\cdot (x+y)$
Găsirea unei submulțimi a mulțimii numerelor întregi al căror produs este un pătrat [10]
Compilarea bazei factorilor: o mulțime , unde p i sunt numere prime astfel încât pentru unele B . $\{ -1, p_1, p_2, \dots, p_n\}$ $p_i \leqslant B$
Cernerea se face ca sita lui Eratosthenes (de unde metoda isi prinde numele). Sita sunt numerele prime ale bazei factorilor și puterile acestora. La cerne, numărul nu este „barat”, ci este împărțit la numărul de la sită. Dacă, prin urmare, numărul s-a dovedit a fi unul, atunci este B - neted.
Ideea principală este că, în loc să iterați peste numere și să verificați dacă pătratele lor sunt divizibile modulo n cu numere prime din baza factorilor, numerele prime din bază sunt sortate și imediat pentru toate numerele de formă se verifică dacă sunt divizibil cu acest număr prim sau cu puterea lui. $x^{2} - n$

Algoritm

Fie un număr compus impar de factorizat. $n$

Alegem gradul unui polinom ireductibil (căci nu va exista un câștig în comparație cu metoda sităi pătratice). $d\ge 3$ $d=2$
Alegem un număr întreg astfel încât și extindem n în bază : $m$ $\lfloor n^{1/(d+1)} \rfloor < m < \lfloor n^{1/d} \rfloor$ $m$ $n = m^d + a_{d-1}m^{d-1} + \dots + a_0$ (unu)
Să asociem cu expansiunea (1) polinomul, ireductibil în inelul de polinoame cu coeficienți întregi $\mathbb Z[x]$ $f_1(x) = x^d + a_{d-1}x^{d-1} + \dots + a_0$
Definim polinomul de cernere ca un polinom omogen în două variabile și : $F_1(a,b)$ $A$ $b$ $F_{1}(a,b)=b^{d}\cdot f_{1}(a/b)=a^{d}+a_{d-1}a^{d-1}b +a_{d-2}a^{d-2}b^{2}+...+a_{0}b^{d}$ (2)
Definim al doilea polinom și polinomul omogen corespunzător . $f_2(x) = x - m$ $F_2(a,b) = a - bm$
Să alegem două numere pozitive și , definind regiunea de cernere (ing. regiune de sită ): $L_1$ $L_2$ $SR = \{1 \le b \le L_1, -L_2 \le a \le L_2 \}$
Să fie o rădăcină . Să considerăm un inel polinomial . Să definim o mulțime numită baza factorilor algebrici , constând din polinoame de ordinul întâi de forma cu norma (2), care este un număr prim. Aceste polinoame sunt câmpuri simple indecompuse în inelul numerelor întregi algebrice . Să limităm valorile absolute ale normelor de polinoame de la o constantă . $\theta$ $f_1(x)$ $\mathbb Z[\theta]$ $FB_1$ $a - b \theta$ $K = \mathbb Q[\theta]$ $FB_1$ $B_1$
Să definim o bază rațională a factorilor , constând din toate numerele prime mărginite de sus de o constantă . $FB_2$ $B_2$
Definim o mulțime numită baza factorilor de caractere pătratice . Este un set de polinoame de ordinul întâi a căror normă este un număr prim. Condiția trebuie îndeplinită . $FB_3$ $c - d \theta$ $FB_1 \cap FB_3 = \empty$
Să efectuăm cernerea polinoamelor după baza factorilor și a numerelor întregi după baza factorilor . Ca rezultat, obținem o mulțime formată din perechi netede , adică astfel de perechi care mcd (a,b) = 1, un polinom și un număr și sunt extinse complet în și, respectiv. $\{a - b \theta \mid (a,b) \in SR\}$ $FB_1$ $\{a - bm \mid (a,b) \in SR\}$ $FB_2$ $M$ $(a,b)$ $(a,b)$ $a - b \theta$ $a-bm$ $FB_1$ $FB_2$
Găsiți un submult astfel încât $S\subseteq M$ $\prod_{(a,b) \in S} Nr(a - b\theta) = H^2 , H \in \mathbb Z ; ~~ \prod_{(a,b) \in S} (a - bm) = B^2 , B \in \mathbb Z$
Să definim un polinom $g(\theta) = {f_1'}^2(\theta) \cdot \prod_{(a,b) \in S} (a - b \theta)$ unde este derivata $f_1'(x)$ $f_1(x)$
Polinomul este un pătrat perfect în inelul polinoamelor . Fie atunci o rădăcină a lui și să fie o rădăcină a lui . $g(\theta)$ $\mathbb Z(\theta)$ $\alpha(\theta)$ $g(\theta)$ $B$ $B^2$
Construim o mapare , înlocuind polinomul cu un număr . Această mapare este un homomorfism inel al inelului de numere întregi algebrice în inel , de unde obținem relația: $\phi \colon \theta \to m$ $\alpha(\theta)$ $\alpha(m)$ $\mathbb Z_K$ $\mathbb Z$ $A^2 = {g(m)}^2 \equiv {\phi(g(\alpha))}^2 \equiv \phi ({f_1'}^2(\theta) \cdot \prod_{(a, b) \in S} (a - b \theta)) \equiv {f_1'}^2(m)\cdot \prod_{(a,b) \in S} (a - bm) \equiv {f_1'} ^2(m) \cdot C^2 \pmod n$
Lasă . Să găsim o pereche de numere astfel încât . Apoi găsim divizorul numărului calculând mcd(n, A ± B), așa cum se face, de exemplu, în metoda sităi pătratice. $B = f'(m) \cdot C$ $(A, B)$ $A \equiv B \pmod n$ $n$

O descriere detaliată a algoritmului poate fi găsită, de exemplu, în [11] și [12] .

Implementări

Până în 2007, software -ul dezvoltat și distribuit de Centrul pentru Matematică și Informatică (CWI) din Țările de Jos, distribuit sub o licență proprietară , a fost considerat cea mai de succes implementare .

În 2007, Jason Papadopoulos a implementat partea finală de procesare a algoritmului, astfel încât să ruleze mai rapid decât versiunea CWI. Acest cod face parte din biblioteca msieve. Msieve este scris în C de Papadopoulos și alții din proiect și include implementări ale metodei de sită generală a câmpului numeric și a metodei de sită pătratică. Distribuit sub drepturi de domeniu public . Suporta calculul distribuit. Cea mai recentă versiune a msieve poate fi găsită pe site-ul autorului .

Alte implementări ale metodei de sită a câmpurilor cu numere generale:

NFS@Home Arhivat 7 decembrie 2012 la Wayback Machine - un proiect de cercetare care a avut ca scop factorizarea numerelor mari folosind metoda sită a câmpului numeric general, folosind o rețea de calculatoare conectate la proiect pentru cernere.
GGNFS Arhivat pe 14 martie 2013 la Wayback Machine , distribuit sub GPL .
pGNFS Arhivat 15 februarie 2013 la Wayback Machine
factor by gnfs Arhivat 12 octombrie 2012 la Wayback Machine
CADO-NFS Arhivat 28 august 2011 la Wayback Machine
kmGNFS Arhivat pe 21 octombrie 2021 la Wayback Machine

Realizări

În 1996, descompunerea numărului RSA-130 a fost obținută folosind algoritmul . Ulterior, folosind metoda, de exemplu, numerele RSA-140 [13] și RSA-155 [14] au fost factorizate . Acesta din urmă a durat peste 8000 de mips ani pentru a se descompune. Pe 9 mai 2005, F. Bahr, M. Bohm, Jens Franke și T. Kleinjung au anunțat că au descompus numărul RSA-200 utilizând metoda sită a câmpului cu numere generale.

În 2009, un grup de oameni de știință din Elveția, Japonia, Franța, Țările de Jos, Germania și Statele Unite au calculat cu succes datele criptate folosind o cheie criptografică RSA de 768 de biți . [15] După cum reiese din descrierea lucrării, calculul valorilor cheie a fost efectuat prin metoda generală a site-ului de câmp numeric. Potrivit cercetătorilor, după munca lor, doar cheile RSA cu o lungime de 1024 de biți sau mai mult pot fi considerate un sistem de criptare fiabil. [16]

Vezi și

Note

↑ Pomerance, Carl. A Tale of Two Sieves (engleză) // Notices of the AMS : journal. - 1996. - Vol. 43 , nr. 12 . - P. 1473-1485 .
↑ JM Pollard (1988), Factorizarea cu numere cubice
↑ A. K. Lenstra, H. W. Lenstra, Jr., MS Manasse, J. M. Pollard (1990), The number field sieve , p. 564-572 , ISBN 0-89791-361-2
↑ Leonard M. Adleman (1991), Factorizarea numerelor folosind numere întregi singulare , p. 64-71, ISBN 0-89791-397-3
↑ A. K. Lenstra, H. W. Lenstra, Jr., MS Manasse, J. M. Pollard. Factorizarea celui de-al nouălea număr Fermat // Math . Comp. : jurnal. - 1993. - Vol. 61 . - P. 319-349 . - doi : 10.1090/S0025-5718-1993-1182953-4 .
↑ JP Buhler, HW Lenstra, Carl Pomerance. Factorizarea numerelor întregi cu sita câmpului numeric (nedefinit) // Note de curs la Matematică. - 1993. - T. 1554 . - S. 50-94 . - doi : 10.1007/BFb0091539 .
↑ Jean-marc Couveignes. Calcularea unei rădăcini pătrate pentru sita câmpului numeric (nedefinită) // Note de curs la matematică. - 1993. - T. 1554 . - S. 95-102 . - doi : 10.1007/BFb0091540 .
↑ A. K. Lenstra, H. W. Lenstra (1993), The Development of the Number Field Sieve , Springer, ISBN 9783540570134
↑ Jean-marc Couveignes. O implementare generală a sită a câmpurilor cu numere (nedefinită) // Note de curs la matematică. - 1993. - T. 1554 . - S. 103-126 . - doi : 10.1007/BFb0091541 .
↑ I. V. Agafonova Factorizarea numerelor întregi mari și criptografia Copie de arhivă din 26 februarie 2015 la Wayback Machine .
↑ Briggs M. (1998), An Introduction to the General Number Field Sieve , < http://www.math.vt.edu/people/brown/doc/briggs_gnfs_thesis.pdf > Arhivat la 8 august 2017 la Wayback Machine
↑ Ishmukhametov Sh. T. Metode de factorizare pentru numere naturale . - Kazan: Kazan. un.. - 2011. - 190 p.
↑ Cavallar S., Dodson B., Lenstra AK, Leyland PC, Lioen WM, Montgomery PL, Murphy B., te Riele HJJ, Zimmerman P. Factorization of RSA-140 using the number field sieve / CWI Report MAS-R9925, September 1999.
↑ Cavallar S., Lioen WM, te Riele HJJ, Dodson B., Lenstra AK, Montgomery PL, Murphy B. et al. Factorizarea modulului RSA de 512 biți / Raport CWI MAS-R0007, februarie 2000.
↑ Anunț de factorizare RSA-768 Arhivat 13 aprilie 2014 la Wayback Machine
↑ Factorizarea RSA-768 Arhivat 13 decembrie 2012 la Wayback Machine