Allmänt nummerfältsållmetod

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 7 december 2019; kontroller kräver 9 redigeringar .

Den allmänna talfältsållmetoden ( engelsk general number field sieve, GNFS) är en faktoriseringsmetod för heltal . Det är den mest effektiva faktoriseringsalgoritmen för tal längre än 110 decimaler. Algoritmens komplexitet uppskattas av den heuristiska formeln [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]

Metoden är en generalisering av den speciella metoden för talfältssilen: medan den senare endast tillåter en att faktorisera tal av något speciellt slag, fungerar den allmänna metoden på mängden heltal, med undantag för primpotenser (som faktoriseras trivialt av slå rötter).

Historik

1988 beskrev den engelske matematikern John Pollard en ny metod för att faktorisera heltal av en speciell form ( ), som illustrerar den med expansionen av det sjunde Fermat-talet . Till skillnad från den kvadratiska siktmetoden , där siktningen utförs på ringen av alla heltal, föreslog metoden att använda ringen av heltal över ett talfält . Manuskriptet bifogades med ett brev adresserat till Andrew Odlyzko , och Richard Brent , John Brillhart , Hendrik Lenstra , Klaus Schnorr och H. Suyama fick också kopior . I detta brev föreslog Pollard att denna metod kanske skulle kunna användas för att utöka det nionde Fermat-numret . [2] $2^n \pm C$ $F_7 = 2^{128}+1$ $Z([2^{3/2}])$ $Q(2^{3/2})$

År 1990 beskrev A. Lenstra , H. Lenstra, Mark Manasse och Pollard den första storskaliga implementeringen av den nya metoden, med några förbättringar. De visade att algoritmen fungerar snabbare på tal av en speciell typ än alla andra kända faktoriseringsmetoder. Tidningen diskuterar också idén om Joe Buhler och Karl Pomerans att förbättra metoden för att bryta ned alla heltal och skisserar lösningen på detta problem. [3]

Senare föreslog Leonard Max Adleman att använda kvadrattecknet för att hitta kvadrater i ett nummerfält. Detta gav en alternativ lösning på problemet som Buchler och Pomerance tog upp och förbättrade den beräknade körtiden för nummerfältssilen när den tillämpades på nummer av ett icke-speciellt slag. [fyra]

Samma år presenterade A. Lenstra, H. Lenstra, Manasse och Pollard expansionen av det nionde Fermat-numret med hjälp av talfältsmetoden. I motsvarande artikel diskuteras många detaljer om denna nedbrytning. [5]

Slutligen, i "Factorizing Integers with the Number Field Sieve", beskrev Buchler, H. Lenstra och Pomerance att talfältssiktmetoden tillämpas på tal som inte nödvändigtvis har en speciell form. [6] Denna implementering av algoritmen inkluderade ett steg som involverade beräkningar med extremt stora tal. Jean-Marc Kuwaignes beskrev i sitt arbete ett sätt att komma runt detta. [7]

Resultaten av den tidiga utvecklingen av metoden sammanfattades av en samling artiklar redigerade av A. Lenstra och H. Lenstra. [8] Samlingen innehöll bland annat en artikel av Bernstein och A. Lenstra, som beskrev en annan förbättrad implementering av algoritmen. Artikeln ingick i samlingen under rubriken "The General Method of the Number Field Sieve". [9]

Kärnan i metoden

Talfältsållmetoden (både speciell och generell) kan tänkas som en förbättring av en enklare metod, den rationella sållmetoden eller den kvadratiska sållmetoden. Algoritmer som liknar dem kräver att man hittar jämna ordningstal . Storleken på dessa siffror växer exponentiellt som . Nummerfältssiktmetoden kräver i sin tur att man hittar jämna tal som är subexponentiella med avseende på storlek. Eftersom dessa siffror är mindre är det mer sannolikt att ett antal av denna storlek kommer att vara jämna, vilket är anledningen till att talfältssiktmetoden är så effektiv. För att uppnå acceleration av beräkningar inom ramen för metoden utförs de i numeriska fält , vilket komplicerar algoritmen, jämfört med en enklare rationell såll. ${\sqrt {n}}$ $n$ $n$

Grundläggande principer

Fermats faktoriseringsmetod för att faktorisera naturliga udda tal n , bestående av att hitta heltal x och y så att , vilket leder till en faktorisering av . $x^{2}-y^{2}=n$ $n=(xy)\cdot (x+y)$
Att hitta en delmängd av mängden heltal vars produkt är en kvadrat [10]
Sammanställning av faktorbasen: en mängd , där p i är primtal så att för vissa B . $\{ -1, p_1, p_2, \dots, p_n\}$ $p_i \leqslant B$
Sållningen görs som sikten från Eratosthenes (därav metoden har fått sitt namn). Silen är primtalen för faktorbasen och deras styrkor. Vid siktning är siffran inte "överstruken", utan delas med siffran från sikten. Om numret som ett resultat visade sig vara ett, så är det B -slät.
Huvudtanken är att istället för att iterera över tal och kontrollera om deras kvadrater är delbara modulo n med primtal från faktorbasen, sorteras primtalen från basen ut och omedelbart för alla tal i formen kontrolleras om de är delbart med detta primtal eller dess potens . $x^{2} - n$

Algoritm

Låt vara ett udda sammansatt tal som ska faktoriseras. $n$

Vi väljer graden av ett irreducerbart polynom (för det blir ingen vinst i jämförelse med den kvadratiska siktmetoden). $d\ge 3$ $d=2$
Vi väljer ett heltal så att , och expanderar n i basen : $m$ $\lgolv n^{1/(d+1)} \rgolv < m < \lgolv n^{1/d} \rgolv$ $m$ $n = m^d + a_{d-1}m^{d-1} + \dots + a_0$ (ett)
Låt oss associera med expansion (1) polynomet, irreducerbart i ringen av polynom med heltalskoefficienter $\mathbb Z[x]$ $f_1(x) = x^d + a_{d-1}x^{d-1} + \dots + a_0$
Vi definierar sållningspolynomet som ett homogent polynom i två variabler och : $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)
Vi definierar det andra polynomet och det motsvarande homogena polynomet . $f_2(x) = x - m$ $F_2(a,b) = a - bm$
Låt oss välja två positiva tal och definiera siktningsregionen (eng. sieve region ): $L_1$ $L_2$ $SR = \{1 \le b \le L_1, -L_2 \le a \le L_2 \}$
Låt vara en rot . Betrakta en polynomring . Låt oss definiera en mängd som kallas den algebraiska faktorbasen , bestående av första ordningens polynom av formen med norm (2), som är ett primtal. Dessa polynom är enkla fält oupplösliga i ringen av algebraiska heltal . Låt oss begränsa de absoluta värdena för normerna för polynom från en konstant . $\theta$ $f_1(x)$ $\mathbb Z[\theta]$ $FB_1$ $a - b \theta$ $K = \mathbb Q[\theta]$ $FB_1$ $B_1$
Låt oss definiera en rationell faktorbas som består av alla primtal som avgränsas uppifrån av en konstant . $FB_2$ $B_2$
Vi definierar en mängd som kallas faktorbasen av kvadratiska tecken . Det är en uppsättning första ordningens polynom vars norm är ett primtal. Villkoret måste vara uppfyllt . $FB_3$ $c - d \theta$ $FB_1 \cap FB_3 = \tom$
Låt oss utföra siktningen av polynom med faktorbasen och heltal med faktorbasen . Som ett resultat får vi en mängd som består av jämna par , det vill säga sådana par att gcd (a,b) = 1, ett polynom och ett tal och expanderas helt i resp . $\{a - b \theta \mid (a,b) \i SR\}$ $FB_1$ $\{a - bm \mid (a,b) \i SR\}$ $FB_2$ $M$ $(a,b)$ $(a,b)$ $a - b \theta$ $a-bm$ $FB_1$ $FB_2$
Hitta en delmängd sådan att $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$
Låt oss definiera ett polynom $g(\theta) = {f_1'}^2(\theta) \cdot \prod_{(a,b) \in S} (a - b \theta)$ var är derivatan $f_1'(x)$ $f_1(x)$
Polynomet är en perfekt kvadrat i ringen av polynom . Låt då vara en rot till och vara en rot till . $g(\theta)$ $\mathbb Z(\theta)$ $\alfa(\theta)$ $g(\theta)$ $B$ $B^2$
Vi konstruerar en mappning och ersätter polynomet med ett tal . Denna mappning är en ringhomomorfism av ringen av algebraiska heltal in i ringen , varifrån vi får förhållandet: $\phi \colon \theta \to m$ $\alfa(\theta)$ $\alfa(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$
Låt . Låt oss hitta ett par siffror så att . Sedan hittar vi talets divisor genom att räkna ut gcd(n, A ± B), som man till exempel gör i kvadratsiktsmetoden. $B = f'(m) \cdot C$ $(A, B)$ $A \equiv B \pmod n$ $n$

En detaljerad beskrivning av algoritmen finns till exempel i [11] och [12] .

Implementeringar

Fram till 2007 ansågs programvara som utvecklats och distribueras av Center for Mathematics and Informatics (CWI) i Nederländerna, distribuerad under en egen licens , vara den mest framgångsrika implementeringen .

År 2007 implementerade Jason Papadopoulos den slutliga bearbetningsdelen av algoritmen så att den gick snabbare än CWI-versionen. Denna kod är en del av msieve-biblioteket. Msieve är skriven i C av Papadopoulos och andra i projektet och inkluderar implementeringar av den allmänna talfältssiktmetoden och den kvadratiska siktmetoden. Distribueras under allmän egendomsrätt . Stöder distribuerad datoranvändning. Den senaste versionen av msieve finns på författarens webbplats .

Några andra implementeringar av den allmänna nummerfältssiktmetoden:

NFS@Home Arkiverad 7 december 2012 på Wayback Machine - ett forskningsprojekt som syftar till att faktorisera stora siffror med hjälp av den allmänna talfältsmetoden, med hjälp av ett nätverk av datorer anslutna till projektet för sållning.
GGNFS Arkiverad 14 mars 2013 på Wayback Machine , distribuerad under GPL .
pGNFS Arkiverad 15 februari 2013 på Wayback Machine
faktor av gnfs Arkiverad 12 oktober 2012 på Wayback Machine
CADO-NFS Arkiverad 28 augusti 2011 på Wayback Machine
kmGNFS Arkiverad 21 oktober 2021 på Wayback Machine

Prestationer

1996 erhölls RSA-130- nummernedbrytningen med hjälp av algoritmen . Senare, med hjälp av metoden, till exempel, faktoriserades siffrorna RSA-140 [13] och RSA-155 [14] . Den senare tog över 8000 mips år att bryta ner. Den 9 maj 2005 tillkännagav F. Bahr, M. Bohm, Jens Franke och T. Kleinjung att de hade dekomponerat RSA-200- numret med den allmänna sifferfältsmetoden.

Under 2009 beräknade en grupp forskare från Schweiz, Japan, Frankrike, Nederländerna, Tyskland och USA framgångsrikt data krypterad med en 768-bitars RSA -krypteringsnyckel. [15] Som följer av beskrivningen av arbetet utfördes beräkningen av nyckelvärden med den allmänna metoden för nummerfältssikten. Enligt forskarna kan endast RSA-nycklar med en längd på 1024 bitar eller mer efter deras arbete betraktas som ett tillförlitligt krypteringssystem. [16]

Se även

Anteckningar

↑ Pomerance, Carl. A Tale of Two Sieves (engelska) // Notices of the AMS : journal. - 1996. - Vol. 43 , nr. 12 . - P. 1473-1485 .
↑ JM Pollard (1988), Factoring med kubiktal
↑ A. K. Lenstra, H. W. Lenstra, Jr., MS Manasse, J. M. Pollard (1990), The number field sieve , sid. 564-572, ISBN 0-89791-361-2
↑ Leonard M. Adleman (1991), Faktorisering av tal med singulära heltal , s. 64-71, ISBN 0-89791-397-3
↑ A. K. Lenstra, H. W. Lenstra, Jr., MS Manasse, J. M. Pollard. Faktoriseringen av det nionde fermatnumret // Math . Comp. : journal. - 1993. - Vol. 61 . - s. 319-349 . - doi : 10.1090/S0025-5718-1993-1182953-4 .
↑ JP Buhler, HW Lenstra, Carl Pomerance. Faktorering av heltal med talfältssilen (obestämd) // Föreläsningsanteckningar i matematik. - 1993. - T. 1554 . - S. 50-94 . - doi : 10.1007/BFb0091539 .
↑ Jean-marc Couveignes. Computing A Square Root For The Number Field Sieve (obestämd) // Lecture Notes in Mathematics. - 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. Implementering av ett generellt antal fältsikter (obestämd) // Lecture Notes in Mathematics. - 1993. - T. 1554 . - S. 103-126 . - doi : 10.1007/BFb0091541 .
↑ I. V. Agafonova Faktorisering av stora heltal och kryptografi Arkivexemplar av 26 februari 2015 på 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 > Arkiverad 8 augusti 2017 på Wayback Machine
↑ Ishmukhametov Sh. T. Faktoriseringsmetoder för naturliga tal . - Kazan: Kazan. un.. - 2011. - 190 sid.
↑ 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. Faktorisering av 512-bitars RSA-modul / CWI-rapport MAS-R0007, februari 2000.
↑ RSA-768 faktoriseringsmeddelande Arkiverad 13 april 2014 på Wayback Machine
↑ RSA-768- faktorisering Arkiverad 13 december 2012 på Wayback Machine