Általános számmezőszita módszer

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. december 7-én felülvizsgált verziótól ; az ellenőrzések 9 szerkesztést igényelnek .

Az általános számmezőszita módszer ( angolul general number field szita , GNFS) egy faktorizációs módszer egész számokra . Ez a leghatékonyabb faktorizációs algoritmus 110 tizedesjegynél hosszabb számokhoz. Az algoritmus összetettségét a heurisztikus képlet [1] becsüli meg.

\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}}\jobbra]

A módszer a számmezőszita speciális módszerének általánosítása: míg ez utóbbi csak valamilyen speciális szám faktorizálását teszi lehetővé, addig az általános módszer egész számok halmazán működik, kivéve a prímek hatványait (amelyeket triviálisan faktorizálunk gyökeret verni).

Történelem

1988- ban John Pollard angol matematikus egy új módszert írt le egy speciális alakú egész számok faktorálására ( ), illusztrálva azt a hetedik Fermat-szám kiterjesztésével . Ellentétben a kvadratikus szita módszerrel , amelyben a szitálást az összes egész szám gyűrűjén hajtják végre, a módszer az egész számok gyűrűjének használatát javasolta egy számmező felett . A kézirathoz mellékelték egy Andrew Odlyzko -nak címzett levelet , és Richard Brent , John Brillhart Lenstra , Klaus Schnorr és H. Suyama is kapott másolatokat . Ebben a levélben Pollard felvetette, hogy talán ezzel a módszerrel lehetne bővíteni a kilencedik Fermat-számot . [2] $2^n \pm C$ $F_7 = 2^{128}+1$ $Z([2^{3/2}])$ $K(2^{3/2})$

1990 -ben A. Lenstra , H. Lenstra, Mark Manasse és Pollard leírták az új módszer első nagyszabású megvalósítását, némi fejlesztéssel. Megmutatták, hogy az algoritmus gyorsabban működik speciális típusú számokon, mint az összes többi ismert faktorizációs módszer. A cikk tárgyalja Joe Buhler és Karl Pomerans ötletét is , hogy javítsák az egész számok lebontásának módszerét, és felvázolja a probléma megoldását. [3]

Később Leonard Max Adleman javasolta a másodfokú karakter használatát a négyzetek számmezőben való kereséséhez. Ez alternatív megoldást kínált a Buchler és Pomerance által felvetett problémára, és javította a számmezőszita becsült futási idejét, ha nem speciális számokra alkalmazták. [négy]

Ugyanebben az évben A. Lenstra, H. Lenstra, Manasse és Pollard bemutatta a kilencedik Fermat-szám számmező módszerrel történő bővítését. A megfelelő cikkben ennek a dekompozíciónak számos részletét tárgyaljuk. [5]

Végül Buchler, H. Lenstra és Pomerance az "Egész számok faktorálása a számmező szitával" című művében leírták a számmezőszita módszert, amely olyan számokra vonatkozik, amelyeknek nem feltétlenül van speciális alakjuk. [6] Az algoritmus ezen megvalósítása tartalmazott egy lépést, amely rendkívül nagy számok felhasználásával végzett számításokat tartalmazott. Jean-Marc Kuwaignes munkájában leírt egy módot ennek megkerülésére. [7]

A módszer korai fejlesztésének eredményeit A. Lenstra és H. Lenstra által szerkesztett cikkgyűjtemény foglalta össze. [8] A gyűjtemény többek között tartalmazta Bernstein és A. Lenstra cikkét, amely az algoritmus egy másik továbbfejlesztett megvalósítását írja le. A cikk „A számmezőszita általános módszere” címszó alatt került be a gyűjteménybe. [9]

A módszer lényege

A számmezőszita módszer (különleges és általános) egy egyszerűbb módszer, a racionális szitamódszer vagy a kvadratikus szitamódszer továbbfejlesztéseként fogható fel. A hozzájuk hasonló algoritmusok sima sorrendszámokat igényelnek . Ezeknek a számoknak a mérete exponenciálisan nő . A számmezőszita módszer viszont megköveteli, hogy olyan sima számokat találjunk, amelyek méretükhöz képest szubexponenciálisak . Mivel ezek a számok kisebbek, valószínűbb, hogy egy ekkora szám sima lesz, ezért olyan hatékony a számmezőszita módszer. A számítások gyorsítása érdekében a módszer keretein belül numerikus mezőkben hajtják végre a számításokat , ami bonyolultabbá teszi az algoritmust egy egyszerűbb racionális szitához képest. ${\sqrt {n}}$ $n$ $n$

Alapelvek

Fermat faktorizálási módszere természetes páratlan számok n faktorizálására , amely az x és y egész számok megtalálásából áll , amely faktorizálásához vezet . $x^{2}-y^{2}=n$ $n=(xy)\cdot (x+y)$
Az egész számok halmazának olyan részhalmazának megkeresése, amelynek szorzata négyzet [10]
A faktorbázis összeállítása: egy halmaz , ahol p i olyan prímszámok, amelyek bizonyos B esetén . $\{ -1, p_1, p_2, \pontok, p_n\}$ $p_i \leqslant B$
A szitálás úgy történik, mint Eratosthenes szitája (innen kapta a módszer a nevét). A szita a faktoralap prímszámai és hatványai. Szűréskor a számot nem „áthúzzuk”, hanem elosztjuk a szitán lévő számmal. Ha ennek eredményeként a szám egynek bizonyult, akkor B -sima.
A lényeg az, hogy ahelyett, hogy számokat iterálnánk, és ellenőriznénk, hogy a négyzetek oszthatók-e modulo n prímszámokkal a faktoralapból, az alapból származó prímszámokat a rendszer kiválogatja, és azonnal az alakzat összes számánál ellenőrzi, hogy osztható ezzel a prímszámmal vagy hatványával . $x^{2} - n$

Algoritmus

Legyen páratlan összetett szám, amelyet faktorizálni kell. $n$

Az irreducibilis polinom fokszámát választjuk (mert nem lesz nyereség a másodfokú szita módszerhez képest). $d\ge 3$ $d=2$
Olyan egész számot választunk , hogy , és kibővítsük az n-t az alapban : $m$ $\lfloor n^{1/(d+1)} \rfloor < m < \lfloor n^{1/d} \rfloor$ $m$ $n = m^d + a_{d-1}m^{d-1} + \pontok + a_0$ (egy)
Társítsuk az (1) bővítéssel az egész együtthatós polinomok gyűrűjében irreducibilis polinomot $\mathbb Z[x]$ $f_1(x) = x^d + a_{d-1}x^{d-1} + \pontok + a_0$
A szitáló polinomot homogén polinomként definiáljuk két változóban és : $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)
Meghatározzuk a második polinomot és a hozzá tartozó homogén polinomot . $f_2(x) = x - m$ $F_2(a,b) = a - bm$
Válasszunk ki két pozitív számot és , meghatározva a szitálási tartományt (angol. szita régió ): $L_1$ $L_2$ $SR = \{1 \le b \le L_1, -L_2 \le a \le L_2 \}$
Legyen gyökér . Tekintsünk egy polinomiális gyűrűt . Határozzuk meg az algebrai faktorbázisnak nevezett halmazt , amely a (2) normával rendelkező elsőrendű polinomokból áll , amely prímszám. Ezek a polinomok egyszerű, az algebrai egész számok gyűrűjében fel nem bontható mezők . Határozzuk meg a polinomok normáinak abszolút értékeit egy konstansból . $\theta$ $f_1(x)$ $\mathbb Z[\theta]$ $FB_1$ $a - b \théta$ $K = \mathbb Q[\theta]$ $FB_1$ $B_1$
Határozzuk meg a racionális faktorbázist , amely minden prímszámból áll , amelyeket felülről egy konstans határol . $FB_2$ $B_2$
Meghatározzuk a másodfokú karakterek faktorbázisának nevezett halmazt . Elsőrendű polinomok halmaza, amelyek normája prímszám. A feltételnek teljesülnie kell . $FB_3$ $c - d \theta$ $FB_1 \cap FB_3 = \üres$
Végezzük el a polinomok faktorbázissal , az egész számok szitálását a faktorbázissal . Ennek eredményeként egy sima párokból álló halmazt kapunk , azaz olyan párokból , amelyek gcd (a,b) = 1, egy polinom és egy szám , és teljes egészében kibővítve vannak , ill. $\{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 \théta$ $a-bm$ $FB_1$ $FB_2$
Keress egy olyan részhalmazt $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$
Definiáljunk egy polinomot $g(\theta) = {f_1'}^2(\theta) \cdot \prod_{(a,b) \in S} (a - b \theta)$ hol van a származéka $f_1'(x)$ $f_1(x)$
A polinom tökéletes négyzet a polinomok gyűrűjében . Legyen akkor a gyökere és legyen a gyökere . $g(\théta)$ $\mathbb Z(\theta)$ $\alpha(\theta)$ $g(\théta)$ $B$ $B^2$
Leképezést készítünk , a polinomot számra cserélve . Ez a leképezés az algebrai egész számok gyűrűjének gyűrűhomomorfizmusa a gyűrűbe , amelyből a következő összefüggést kapjuk: $\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$
Hadd . Keressünk egy olyan számpárt , amelyre . Ezután a gcd(n, A ± B) kiszámításával megtaláljuk a szám osztóját , ahogyan például a másodfokú szita módszernél is megteszik. $B = f'(m) \cdot C$ $(A, B)$ $A \equiv B \pmod n$ $n$

Az algoritmus részletes leírása megtalálható például a [11]-ben és a [12]-ben .

Megvalósítások

2007- ig a hollandiai Matematikai és Informatikai Központ (CWI) által kifejlesztett és terjesztett , védett licenc alatt terjesztett szoftver számított a legsikeresebb megvalósításnak .

2007 -ben Jason Papadopoulos megvalósította az algoritmus végső feldolgozási részét, így az gyorsabban futott, mint a CWI verzió. Ez a kód a msieve könyvtár része. Az Msieve-et C nyelven írták Papadopoulos és mások a projektben , és tartalmazza az általános számmezőszita módszer és a kvadratikus szita módszer megvalósítását. Köztulajdonjogok alatt terjesztve . Támogatja az elosztott számítástechnikát. Az msieve legújabb verziója megtalálható a szerző honlapján .

Az általános számmező szita módszer néhány további megvalósítása:

NFS@Home archiválva 2012. december 7-én a Wayback Machine -nél – egy kutatási projekt, amelynek célja nagy számok faktorálása az általános számmezőszita módszerrel, a projekthez csatlakoztatott számítógépek hálózatának felhasználásával szitálás céljából.
GGNFS archiválva 2013. március 14-én a Wayback Machine -nél, GPL alatt terjesztve .
pGNFS archiválva : 2013. február 15. a Wayback Machine -nél
faktor, szerző: gnfs Archiválva : 2012. október 12., a Wayback Machine -nél
CADO-NFS archiválva : 2011. augusztus 28. a Wayback Machine -nél
kmGNFS archiválva 2021. október 21-én a Wayback Machine -nél

Eredmények

1996-ban az RSA-130 számfelbontást az algoritmussal kapták meg . Később a módszerrel például az RSA-140 [13] és az RSA-155 [14] számokat faktorizálták . Ez utóbbi több mint 8000 mips év alatt bomlott le. 2005. május 9- én F. Bahr, M. Bohm, Jens Franke és T. Kleinjung bejelentették, hogy az általános számmezőszita módszerrel bontották az RSA-200 számot.

2009-ben Svájcból, Japánból, Franciaországból, Hollandiából, Németországból és az Egyesült Államokból származó tudósok egy csoportja sikeresen kiszámította a 768 bites RSA kriptográfiai kulccsal titkosított adatokat. [15] Amint az a munka leírásából következik, a kulcsértékek kiszámítása a számmezőszita általános módszerével történt. A kutatók szerint munkájuk után csak az 1024 bites vagy annál hosszabb RSA kulcsok tekinthetők megbízható titkosítási rendszernek. [16]

Lásd még

Jegyzetek

↑ Pomerance, Carl. A Tale of Two Sieves (angol) // Notices of the AMS : Journal. - 1996. - 1. évf. 43 , sz. 12 . - P. 1473-1485 .
↑ JM Pollard (1988), Faktorozás köbszámokkal
↑ A. K. Lenstra, H. W. Lenstra, Jr., MS Manasse, J. M. Pollard (1990), The number field szita , p. 564-572, ISBN 0-89791-361-2
↑ Leonard M. Adleman (1991), Számok faktorálása szinguláris egész számok használatával , p. 64-71, ISBN 0-89791-397-3
↑ A. K. Lenstra, H. W. Lenstra, Jr., MS Manasse, J. M. Pollard. A kilencedik Fermat-szám faktorizálása // Math . Összeg. : folyóirat. - 1993. - 1. évf. 61 . - 319-349 . - doi : 10.1090/S0025-5718-1993-1182953-4 .
↑ JP Buhler, HW Lenstra, Carl Pomerance. Egész számok faktorálása a számmező szitával (határozatlan) // Matematikai előadásjegyzetek. - 1993. - T. 1554 . - S. 50-94 . - doi : 10.1007/BFb0091539 .
↑ Jean-marc Couveignes. Négyzetgyök kiszámítása a számmező szitához (határozatlan) // Matematikai előadásjegyzetek. - 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. Egy általános számmezőszita megvalósítás (határozatlan) // Lecture Notes in Mathematics. - 1993. - T. 1554 . - S. 103-126 . - doi : 10.1007/BFb0091541 .
↑ I. V. Agafonova Nagy egészek faktorizálása és kriptográfia 2015. február 26-i archív másolat a Wayback Machine -nél .
↑ Briggs M. (1998), An Introduction to the General Number Field Sieve , < http://www.math.vt.edu/people/brown/doc/briggs_gnfs_thesis.pdf > Archivált : 2017. augusztus 8. a Wayback Machine -nél
↑ Ishmukhametov Sh. T. Faktorizációs módszerek természetes számokra . - 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. Az RSA-140 faktorizálása a számmezőszitával / CWI Report MAS-R9925, szeptember 1999.
↑ Cavallar S., Lioen WM, te Riele HJJ, Dodson B., Lenstra AK, Montgomery PL, Murphy B. et al. Az 512 bites RSA-modulus faktorizálása / CWI jelentés MAS-R0007, 2000. február.
↑ RSA-768 faktorizációs bejelentés archiválva : 2014. április 13. a Wayback Machine -nél
↑ RSA-768 faktorizáció archiválva : 2012. december 13. a Wayback Machine -nél