Obecná metoda číselného pole síta

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 7. prosince 2019; kontroly vyžadují 9 úprav .

Metoda síta obecných čísel ( anglicky general number field sieve , GNFS) je metoda faktorizace pro celá čísla . Je to nejúčinnější faktorizační algoritmus pro čísla delší než 110 desetinných míst. Složitost algoritmu se odhaduje pomocí heuristického vzorce [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]

Tato metoda je zobecněním speciální metody síta číselných polí: zatímco druhá umožňuje pouze faktorizovat čísla nějakého speciálního druhu, obecná metoda pracuje na množině celých čísel, s výjimkou mocnin prvočísel (která jsou faktorizována triviálně zakořenění).

Historie

V roce 1988 anglický matematik John Pollard popsal novou metodu faktorizace celých čísel speciálního tvaru ( ), ilustrující ji rozšířením sedmého Fermatova čísla . Na rozdíl od metody kvadratického síta , ve které se prosévání provádí na kruhu všech celých čísel, metoda navrhla použít kruh celých čísel nad číselným polem . Rukopis byl přiložen k dopisu adresovanému Andrew Odlyzko a kopie obdrželi také Richard Brent , John Brillhart , Hendrik Lenstra , Klaus Schnorr a H. Suyama . V tomto dopise Pollard navrhl, že by tato metoda mohla být použita k rozšíření devátého Fermatova čísla . [2] $2^n \pm C$ $F_7 = 2^{128}+1$ $Z([2^{3/2}])$ $Q(2^{3/2})$

V roce 1990 popsali A. Lenstra , H. Lenstra, Mark Manasse a Pollard první rozsáhlou implementaci nové metody s některými vylepšeními. Ukázali, že algoritmus pracuje rychleji na číslech speciálního typu než všechny ostatní známé metody faktorizace. Článek také pojednává o myšlence Joe Buhlera a Karla Pomeranse zlepšit metodu rozkladu jakýchkoli celých čísel a nastiňuje řešení tohoto problému. [3]

Později Leonard Max Adleman navrhl použití kvadratického znaku k nalezení čtverců v číselném poli. To poskytlo alternativní řešení problému vzneseného Buchlerem a Pomerancem a zlepšilo odhadovanou dobu běhu síta číselného pole při aplikaci na čísla nespeciálního druhu. [čtyři]

Ve stejném roce představili A. Lenstra, H. Lenstra, Manasse a Pollard rozšíření devátého Fermatova čísla metodou číselného pole. V odpovídajícím článku je diskutováno mnoho podrobností o tomto rozkladu. [5]

Konečně v „Factorizing Integers with the Number Field Sieve“ Buchler, H. Lenstra a Pomerance popsali metodu síta číselných polí, jak je aplikována na čísla, která nemusí mít nutně speciální tvar. [6] Tato implementace algoritmu zahrnovala krok zahrnující výpočty s extrémně velkými čísly. Jean-Marc Kuwaignes ve své práci popsal způsob, jak to obejít. [7]

Výsledky raného vývoje metody byly shrnuty ve sborníku článků editovaných A. Lenstrou a H. Lenstrou. [8] Sbírka mimo jiné obsahovala článek Bernsteina a A. Lenstra, popisující další vylepšenou implementaci algoritmu. Článek byl zařazen do sborníku pod názvem "Obecná metoda číselného polního síta". [9]

Podstata metody

Metodu číselného síta (speciální i obecnou) lze považovat za vylepšení jednodušší metody, metody racionálního síta nebo metody kvadratického síta. Algoritmy jim podobné vyžadují nalezení hladkých čísel pořadí . Velikost těchto čísel roste exponenciálně jako . Metoda síta číselných polí zase vyžaduje nalezení hladkých čísel, která jsou subexponenciální s ohledem na velikost. Protože jsou tato čísla menší, je pravděpodobnější, že číslo této velikosti bude hladké, a proto je metoda číselného pole síta tak účinná. Pro zrychlení výpočtů v rámci metody jsou prováděny v numerických polích , což algoritmus komplikuje oproti jednoduššímu racionálnímu sítu. ${\sqrt {n}}$ $n$ $n$

Základní principy

Fermatova faktorizační metoda pro rozklad přirozených lichých čísel n , spočívající v nalezení celých čísel x a y takových, že , což vede k rozkladu na . $x^{2}-y^{2}=n$ $n=(xy)\cdot (x+y)$
Hledání podmnožiny množiny celých čísel, jejichž součin je čtverec [10]
Sestavení základu faktoru: a množina , kde p i jsou prvočísla taková, že pro nějaké B . $\{ -1, p_1, p_2, \tečky, p_n\}$ $p_i \leqslant B$
Prosévání se provádí jako Eratosthenovo síto (odtud tato metoda dostala svůj název). Síto jsou prvočísla faktorové báze a jejich mocniny. Při prosévání se číslo „neškrtá“, ale dělí se číslem ze síta. Pokud se v důsledku toho číslo ukázalo jako jedna, pak je B -hladké.
Hlavní myšlenkou je, že místo iterování čísel a kontroly, zda jsou jejich druhé mocniny dělitelné modulo n prvočísly z faktorové základny, se prvočísla ze základu vytřídí a hned se pro všechna čísla tvaru zkontroluje, zda jsou dělitelný tímto prvočíslem nebo jeho mocninou . $x^{2} - n$

Algoritmus

Nechť je liché složené číslo, které má být faktorizováno. $n$

Zvolíme stupeň ireducibilního polynomu (neboť ve srovnání s metodou kvadratického síta nebude zisk). $d\ge 3$ $d=2$
Zvolíme celé číslo takové, že , a rozbalíme n v základu : $m$ $\lpodlaží n^{1/(d+1)} \rpodlaží < m < \lpatro n^{1/d} \rpodlaží$ $m$ $n = m^d + a_{d-1}m^{d-1} + \dots + a_0$ (jeden)
Spojme s expanzí (1) polynom, neredukovatelný v okruhu polynomů s celočíselnými koeficienty $\mathbb Z[x]$ $f_1(x) = x^d + a_{d-1}x^{d-1} + \dots + a_0$
Prosévací polynom definujeme jako homogenní polynom ve dvou proměnných a : $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)
Definujeme druhý polynom a odpovídající homogenní polynom . $f_2(x) = x - m$ $F_2(a,b) = a - bm$
Zvolme dvě kladná čísla a , definující oblast síta (eng. sieve region ): $L_1$ $L_2$ $SR = \{1 \le b \le L_1, -L_2 \le a \le L_2 \}$
Nechť být kořenem . Uvažujme polynomiální kruh . Definujme množinu zvanou algebraický faktor základ , skládající se z polynomů prvního řádu ve tvaru s normou (2), což je prvočíslo. Tyto polynomy jsou jednoduchá pole nerozložitelná v kruhu algebraických celých čísel . Omezme absolutní hodnoty norem polynomů z konstanty . $\theta$ $f_1(x)$ $\mathbb Z[\theta]$ $FB_1$ $a - b \theta$ $K = \mathbb Q[\theta]$ $FB_1$ $B_1$
Definujme základ racionálního faktoru , skládající se ze všech prvočísel ohraničených shora konstantou . $FB_2$ $B_2$
Definujeme množinu zvanou faktorová báze kvadratických znaků . Je to množina polynomů prvního řádu, jejichž normou je prvočíslo. Podmínka musí být splněna . $FB_3$ $c - d \theta$ $FB_1 \cap FB_3 = \prázdné$
Proveďme prosévání polynomů faktorovým základem a celých čísel faktorovým základem . Výsledkem je množina sestávající z hladkých dvojic , tedy takových dvojic , které gcd (a,b) = 1, polynom a číslo a jsou zcela rozšířeny v resp . $\{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$
Najděte takovou podmnožinu , že $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$
Definujme polynom $g(\theta) = {f_1'}^2(\theta) \cdot \prod_{(a,b) \in S} (a - b \theta)$ kde je derivace $f_1'(x)$ $f_1(x)$
Polynom je dokonalý čtverec v kruhu polynomů . Nechť pak být kořenem a být kořenem . $g(\theta)$ $\mathbb Z(\theta)$ $\alpha(\theta)$ $g(\theta)$ $B$ $B^2$
Sestrojíme zobrazení a nahradíme polynom číslem . Toto zobrazení je kruhový homomorfismus kruhu algebraických celých čísel do kruhu , odkud dostáváme vztah: $\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$
Nechte _ Pojďme najít dvojici čísel tak, že . Potom najdeme dělitele čísla výpočtem gcd(n, A ± B), jak se to dělá například v metodě kvadratického síta. $B = f'(m) \cdot C$ $(A, B)$ $A \equiv B \pmod n$ $n$

Podrobný popis algoritmu lze nalézt např. v [11] a [12] .

Implementace

Do roku 2007 byl za nejúspěšnější implementaci považován software vyvinutý a distribuovaný Centrem pro matematiku a informatiku (CWI) v Nizozemsku, distribuovaný pod proprietární licencí .

V roce 2007 implementoval Jason Papadopoulos finální část zpracování algoritmu tak, aby běžel rychleji než verze CWI. Tento kód je součástí knihovny msieve. Msieve je napsáno v C od Papadopoulos a dalších na projektu a zahrnuje implementace metody obecného číselného pole a metody kvadratického síta. Distribuováno pod právy veřejné domény . Podporuje distribuované výpočty. Nejnovější verzi msieve lze nalézt na stránkách autora .

Některé další implementace metody obecného číselného pole síta:

NFS@Home Archivováno 7. prosince 2012 na Wayback Machine - výzkumný projekt zaměřený na faktorizaci velkých čísel pomocí metody obecného číselného pole síta, pomocí sítě počítačů připojených k projektu pro prosévání.
GGNFS Archivováno 14. března 2013 na Wayback Machine , distribuovaném pod licencí GPL .
pGNFS Archivováno 15. února 2013 na Wayback Machine
factor by gnfs Archivováno 12. října 2012 na Wayback Machine
CADO-NFS Archivováno 28. srpna 2011 na Wayback Machine
kmGNFS Archivováno 21. října 2021 na Wayback Machine

Úspěchy

V roce 1996 byl pomocí algoritmu získán rozklad čísel RSA-130 . Později byla pomocí metody např. faktorizována čísla RSA-140 [13] a RSA-155 [14] . Tomu druhému trvalo více než 8000 mips let, než se rozložil. Dne 9. května 2005 F. Bahr, M. Bohm, Jens Franke a T. Kleinjung oznámili, že rozložili číslo RSA-200 pomocí metody obecného číselného pole.

V roce 2009 skupina vědců ze Švýcarska, Japonska, Francie, Nizozemska, Německa a Spojených států úspěšně vypočítala data zašifrovaná pomocí 768bitového kryptografického klíče RSA . [15] Jak vyplývá z popisu práce, výpočet klíčových hodnot byl proveden obecnou metodou číselného pole síta. Podle vědců lze po jejich práci považovat za spolehlivý šifrovací systém pouze klíče RSA s délkou 1024 bitů a více. [16]

Viz také

Poznámky

↑ Pomerance, Carl. A Tale of Two Sieves (anglicky) // Notices of the AMS : journal. - 1996. - Sv. 43 , č. 12 . - S. 1473-1485 .
↑ JM Pollard (1988), Faktorování s kubickými čísly
↑ A. K. Lenstra, H. W. Lenstra, Jr., MS Manasse, J. M. Pollard (1990), The number field sive , str. 564-572, ISBN 0-89791-361-2
↑ Leonard M. Adleman (1991), Rozdělení čísel pomocí singulárních celých čísel , str. 64-71, ISBN 0-89791-397-3
↑ A. K. Lenstra, H. W. Lenstra, Jr., MS Manasse, J. M. Pollard. Faktorizace devátého Fermatova čísla // Matematika . Comp. : deník. - 1993. - Sv. 61 . - str. 319-349 . - doi : 10.1090/S0025-5718-1993-1182953-4 .
↑ JP Buhler, HW Lenstra, Carl Pomerance. Rozdělení celých čísel pomocí síta číselného pole (neurčité) // Poznámky z přednášky z matematiky. - 1993. - T. 1554 . - S. 50-94 . - doi : 10.1007/BFb0091539 .
↑ Jean-marc Couveignes. Výpočet druhé odmocniny pro síto číselného pole (neurčeno) // Poznámky z přednášky z matematiky. - 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. Implementace obecného číselného pole síta (neurčité) // Poznámky z přednášky z matematiky. - 1993. - T. 1554 . - S. 103-126 . - doi : 10.1007/BFb0091541 .
↑ I. V. Agafonova Faktorizace velkých celých čísel a kryptografie Archivní kopie z 26. února 2015 na 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 > Archivováno 8. srpna 2017 na Wayback Machine
↑ Ishmukhametov Sh. T. Faktorizační metody pro přirozená čísla . - Kazaň: Kazaň. un.. - 2011. - 190 s.
↑ Cavallar S., Dodson B., Lenstra AK, Leyland PC, Lioen WM, Montgomery PL, Murphy B., te Riele HJJ, Zimmerman P. Faktorizace RSA-140 pomocí číselného pole síta / CWI Report MAS-R9925, září 1999.
↑ Cavallar S., Lioen WM, te Riele HJJ, Dodson B., Lenstra AK, Montgomery PL, Murphy B. et al. Faktorizace 512bitového modulu RSA / zpráva CWI MAS-R0007, únor 2000.
↑ Oznámení faktorizace RSA-768 Archivováno 13. dubna 2014 na Wayback Machine
↑ Faktorizace RSA-768 Archivováno 13. prosince 2012 na Wayback Machine