Különleges számú mezőszita módszer

A speciális számmezőszita módszer ( angolul special number field szita , SNFS) egy speciális típusú egész számok faktorálási módszere. Ebből származtatták az általános számmező szita módszert , amely a leghatékonyabb faktorizációs algoritmus nagy egész számok esetén . A módszer r e ± s alakú egész számokra hatásos , ahol r N s Z, r és s kicsik (pl . Mersenne-számok ). $n>10^{{110}}$ $\ban ben$ $\ban ben$

Az n szám faktorizálásának összetettségének heurisztikus becslését az [1] képlet fejezi ki :

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

SNFS segítségével a 155 tizedesjegyből álló Fermat-számot [2] faktorizáltuk . $F_{9}=2^{512}+1$

Eredet

A módszer alapötletét először John Pollard cikkében [3] amelyet 1988-ban küldött el kollégáinak. Ebben a hetedik Fermat-számon illusztrálta módszerét . Az ötlet az volt, hogy a rostálást ne egész számok gyűrűjén végezzük, mint a másodfokú szita módszernél , hanem egy algebrai számmezőn. 1990-ben ezzel a módszerrel bontották fel a kilencedik Fermat-számot . A módszer kezdetben csak speciális 2 n ± c alakú számokra volt alkalmazható , ezért nevezték "speciális számmezőszita módszernek". A módszert később tetszőleges számokra módosították és általános numerikus szita módszernek nevezték el . $2^{128}+1$ $F_{9}=2^{512}+1$

Módszer áttekintése

Az SNFS az egyszerűbb racionális szita módszeren alapul . Javasoljuk, hogy az olvasó ismerkedjen meg ezzel a módszerrel, mielőtt megismerné az SNFS-t.

Az SNFS így működik. Legyen n az a szám, amelyet a faktorizáláshoz kell tenni. A racionális szita módszerhez hasonlóan az SNFS algoritmus két lépésre bontható:

A Z / n Z faktorbázis szorzóarányainak számának meghatározása nagyobb, mint a faktorbázis elemeinek száma.
Az arányokat úgy megszorozzuk egymás között, hogy a kapott szorzatok fokozatai azonosak legyenek, azaz a 2 ≡ b 2 ( mod n ) alakú arányokat kapjunk . Ez viszont n faktorizációjához vezet : n = gcd ( a + b , n ) × gcd( a - b , n ). Ha a kapott dekompozíció triviális (azaz n = n × 1), akkor keresnünk kell az összefüggések további szorzatait, amelyek kielégítik ezt a feltételt.

A második lépés megegyezik a racionális szita módszer lépésével, és egy lineáris algebrai feladat . Ellentétben az első lépéssel, amely ennél a módszernél hatékonyabb.

A módszer részletei

Legyen n faktorizálható szám. Vegyünk egy f irreducibilis polinomot és egy m egész számot , amelyekre f ( m ) ≡ 0 ( mod n ) (a választásuk alapelveit a következő részben magyarázzuk el). Legyen α f gyöke ; akkor van egy Z [α] gyűrű . Ezután van egy egyedi homomorfizmusgyűrű φ Z [ α ] és Z /n Z között , amely leképezi α -t m -re . Az egyszerűség kedvéért feltételezzük, hogy Z [ α ] faktoriális gyűrű ; a módszer módosítható arra az esetre, ha ez a feltétel nem teljesül, ami további számításokhoz vezet.

Ezután létrehozunk két faktorbázist , egyet Z [ α ] -hoz, egyet pedig Z -hez. A Z [ α ] faktorbázis tartalmazza az összes Z [ α ] prímet , amelynek mérete korlátozott . A Z faktorbázis , akárcsak a racionális szita módszernél, prímszámokból áll valamilyen határszámig. ${\displaystyle N_{\max ))$

Ezután keresünk olyan másodpímszámokat ( a , b ), hogy:

a + bm sima a Z faktorbázisának elemeihez képest (vagyis minden prímosztóját a faktorbázis tartalmazza).
a + bα sima a Z faktorbázis elemeihez képest [ α ], abból a módból, ahogyan a faktorbázis elemeit választottuk, ez a feltétel ekvivalens azzal, hogy a + bα csak kisebb prímszámokkal osztható, mint . ${\displaystyle N_{\max ))$

Ezeket a számpárokat Eratoszthenész szitájához hasonló szitálási módszerrel találjuk meg ; ez magyarázza a számmező szita módszer nevét.

Minden ilyen számpárra ( a , b ) alkalmazhatjuk a φ homomorfizmus gyűrűt a + bα faktorizálására és a kanonikus homomorfizmus gyűrűt Z -ről Z /n Z -re az a + bm faktorizálására . Ezeket egyenlítve multiplikatív összefüggéseket kapunk a Z /n Z faktorbázis elemeire . Miután elegendő számú ilyen arányt találtunk, a fent leírtak szerint megszorozzuk őket egymás között.

Választási lehetőségek

Nem minden szám alkalmas az SNFS módszerrel történő faktorizálásra: előre meg kell találni egy megfelelő fokú f polinomot (az optimális fokot feltételezzük ; az adott pillanatban faktorizálható számoknál N 4,5 vagy 6) kis együtthatók és x úgy, hogy ahol N a faktorizálás száma. Az x -nek is olyannak kell lennie, hogy a- ra és b-re érvényes legyen, ne legyen nagy . $\left(3{\frac {\log N}{\log \log N}}\right)^{1/3}$ $f(x)\equiv 0{\pmod {N))$ $ax+b\equiv 0{\pmod {N))$ ${\displaystyle N^{1/d))$

Az egyik olyan számtípus, amelyre ilyen polinomok léteznek, a következő alakú számok ; például amikor az NFSNET felbontotta a 3^479+1 számot, az x^6+3 polinomot használta az x=3^80-hoz, mert (3^80)^6+3 = 3^480+3 és . $a^{b}\pm 1$ $3^{480}+3\equiv 0{\pmod {3^{479}+1))$

A lineáris ismétlődési relációk által meghatározott számok, mint például a Fibonacci-számok és a Lucas-számok is rendelkeznek SNFS-polinomokkal, de ezeket egy kicsit nehezebb megszerezni. Például van egy polinomja és egy x értéke , amely kielégíti a . [négy] $F_{709}$ $n^{5}+10n^{3}+10n^{2}+10n+3$ $F_{142}x-F_{141}=0$

Ha ismeri egy nagy SNFS-szám néhány osztóját, akkor a többihez SNFS-számításokat végezhet; a fenti példában az NFSNET-ből 3^479+1 = (4 158071 7167757 7759574882776161031) szorozva egy 197 jegyű összetett számot (a kis osztókat az ECM módszerrel eltávolítottuk ), és az SNFS-t egy 197-es számjegyhez alkalmaztuk. Az NFS-hez tartozó műveletek száma az eredeti szám méretétől függ, de egyes számítások gyorsabbak egy kisebb számnál.

Korlátozások

Ez a módszer, amint fentebb megjegyeztük, nagyon hatékony r e ± s alakú számok esetén , ahol r és s viszonylag kicsik. Hatásos olyan számokra is, amelyek kis együtthatókkal polinomként ábrázolhatók. A helyzet az, hogy a speciális számmező szita módszer két számmezőre szitál. A módszer hatékonysága nagymértékben függ ezeken a területeken az egyes elemek méretétől. Ha egy szám kis együtthatójú polinomként ábrázolható, akkor a kiszámított számok sokkal kisebbek, mint azok a számok, amelyekkel akkor kell foglalkozni, ha ilyen polinom nem létezik.

Lásd még

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

Jegyzetek

↑ Pomerance, Carl (1996. december), A Tale of Two Sieves , Notices of the AMS vol . 43 (12): 1473–1485 , < http://www.ams.org/notices/199612/pomerance.pdf > Archivált 2020. november 11-én kelt példány a Wayback Machine -nél
↑ Vaszilenko, O.N. (2003), Számelméleti kriptográfiai algoritmusok , p. 93-107 , < http://www.ict.edu.ru/ft/002416/book.pdf > Archiválva 2007. január 27-én a Wayback Machine -nél
↑ Pollard, JM (1988), Faktorozás köbszámokkal
↑ Franke, Jens A ggnfs-lasieve4 telepítési megjegyzései . MIT Massachusetts Institute of Technology. Letöltve: 2011. december 4. Az eredetiből archiválva : 2012. szeptember 5.. (határozatlan)

Irodalom

Ismukhametov, Sh.T. (2011), Faktorizációs módszerek természetes számokra , p. 145-175 , < http://window.edu.ru/window_catalog/files/r73980/Monograph_ishm.pdf > (a hivatkozás nem érhető el)
Byrnes, Steven (2005. május 18.), The Number Field Sieve , Math 129 , < http://modular.fas.harvard.edu/129-05/final_papers/Steve_Byrnes.pdf > . Letöltve: 2011. december 4. Archiválva : 2006. szeptember 20. a Wayback Machine -nél
Lenstra, A. K .; Lenstra, HW, Jr. ; Manasse, MS & Pollard, JM (1993), The Factorization of the Ninth Fermat Number , Mathematics of Computation 61 (203): 319–349, doi : 10.1090/S0025-5718-1993-1182953 , < http: //www.std.org/~msm/common/f9paper.ps > Archiválva : 2012. február 4. a Wayback Machine -nél
Lenstra, A.K. & Lenstra, HW, Jr., szerk. (1993), The Development of the Number Field Sieve , vol. 1554, Lecture Notes in Mathematics, New York: Springer-Verlag, ISBN 3540570136
Silverman, Robert D. (2007), Optimal Parameterization of SNFS, J. Mathematical Cryptology (de Gruyter). – 1. köt.: 105–124

Linkek

NFS@Home