Speciell nummerfältsållmetod

Special number field sieve-metoden ( engelska special number field sieve , SNFS) är en metod för att faktorisera heltal av ett speciellt slag. Från den härleddes den allmänna talfältssiktmetoden , som är den mest effektiva faktoriseringsalgoritmen för stora heltal . Metoden är effektiv för heltal av formen r e ± s , där r N s Z, r och s är små (t.ex. Mersenne-tal ). $n>10^{{110}}$ $\i$ $\i$

Den heuristiska uppskattningen av komplexiteten av faktorisering av talet n uttrycks med formeln [1] :

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

Med SNFS faktoriserades Fermat-numret med 155 decimalsiffror [2] . $F_{9}=2^{512}+1$

Origins

Grundidén med metoden föreslogs först John Pollard sin artikel [3] som han skickade till sina kollegor 1988. I den illustrerade han sin metod på det sjunde Fermat-numret . Tanken var att utföra siktningen inte på en ring av heltal, som i kvadratisk siktmetoden , utan på ett algebraiskt talfält. 1990 bröts det nionde Fermat-numret ned med denna metod . Inledningsvis var metoden endast tillämpbar för nummer av en speciell form 2 n ± c , varför den kallades för "specialnummerfältsållmetoden". Metoden modifierades senare för godtyckliga siffror och döptes till den allmänna numeriska siktmetoden . $2^{128}+1$ $F_{9}=2^{512}+1$

Metodöversikt

SNFS bygger på den enklare rationella sållmetoden . Läsaren uppmanas att bekanta sig med denna metod innan de lär sig om SNFS.

SNFS fungerar så här. Låt n vara talet som ska faktoriseras. I likhet med den rationella siktmetoden kan SNFS-algoritmen delas upp i två steg:

Hitta antalet multiplikationsförhållanden för faktorbasen Z / n Z större än antalet element i faktorbasen.
Multiplicera kvoterna sinsemellan på ett sådant sätt att graderna av de resulterande produkterna är desamma, det vill säga erhålla förhållanden av formen a 2 ≡ b 2 ( mod n ). Detta leder i sin tur till en faktorisering av n : n = gcd ( a + b , n ) × gcd( a - b , n ). Om den erhållna nedbrytningen är trivial (det vill säga n = n × 1), bör man leta efter andra produkter av relationer som uppfyller detta villkor.

Det andra steget är identiskt med steget i den rationella siktmetoden och är ett linjärt algebraproblem . Till skillnad från det första steget, som i denna metod är mer effektivt.

Metoddetaljer

Låt n vara ett faktoriserbart tal. Ta ett irreducerbart polynom f och ett heltal m så att f ( m ) ≡ 0 ( mod n ) (principerna för att välja dem kommer att förklaras i nästa avsnitt). Låt α vara roten till f ; då finns det en ring Z [α]. Sedan finns det en unik homomorfismring φ mellan Z [ α ] och Z /n Z som mappar α till m . För enkelhetens skull antar vi att Z [ α ] är en faktoriell ring ; metoden kan modifieras för de fall då detta villkor inte är uppfyllt, vilket kommer att leda till ytterligare beräkningar.

Sedan skapar vi två faktorbaser , en för Z [ α ] och en för Z. Faktorbasen Z [ α ] innehåller alla primtal Z [ α ] vars storlek är begränsad av . Faktorbasen Z , som i den rationella siktmetoden, består av primtal upp till något gränstal. ${\displaystyle N_{\max ))$

Sedan letar vi efter coprimtal ( a , b ) så att:

a + bm är jämn med avseende på elementen i faktorbasen för Z (det vill säga alla dess primtalsdelare ingår i faktorbasen).
a + bα är jämn med avseende på elementen i faktorbasen Z [ α ]; från det sätt vi valde elementen i faktorbasen är detta villkor ekvivalent med det faktum att a + bα är delbart endast med primtal mindre än . ${\displaystyle N_{\max ))$

Dessa par av siffror hittas genom en sållningsmetod som liknar Eratosthenes såll ; detta förklarar namnet på talfältsållmetoden.

För varje sådant par av tal ( a , b ) kan vi tillämpa homomorfismringen φ för att faktorisera a + bα och den kanoniska homomorfismringen från Z till Z /n Z för att faktorisera a + bm . Genom att likställa dem får vi multiplikativa relationer för elementen i faktorbasen Z /n Z . Efter att ha hittat ett tillräckligt antal sådana förhållanden multiplicerar vi dem sinsemellan enligt beskrivningen ovan.

Val av alternativ

Inte alla tal är lämpliga för faktorisering med SNFS-metoden: det är nödvändigt att i förväg hitta ett polynom f av lämplig grad (den optimala graden antas vara ; för tal som kan faktoriseras vid det givna ögonblicket är N 4,5 eller 6) med små koefficienter och x så att , där N är talet för faktorisering . Även x måste vara sådan att det gäller för a och b inte stora . $\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))$

En av de typer av tal som sådana polynom finns för är nummer av formen ; till exempel, när NFSNET dekomponerade talet 3^479+1 använde de x^6+3-polynomet för x=3^80, eftersom (3^80)^6+3 = 3^480+3 och . $a^{b}\pm 1$ $3^{480}+3\equiv 0{\pmod {3^{479}+1))$

Tal definierade av linjära återkommande relationer, som Fibonacci-tal och Lucas-tal , har också SNFS-polynom, men de är lite svårare att få fram. Har till exempel ett polynom och ett x -värde som uppfyller . [fyra] $F_{709}$ $n^{5}+10n^{3}+10n^{2}+10n+3$ $F_{142}x-F_{141}=0$

Om du känner till några divisorer för ett stort SNFS-tal kan du göra SNFS-beräkningar för resten; för exemplet ovan från NFSNET, 3^479+1 = (4 158071 7167757 7759574882776161031) gånger ett 197-siffrigt sammansatt nummer (små delare eliminerades med ECM -metoden ), och SNFS användes för ett 197-siffrigt tal. Antalet operationer för NFS beror på storleken på det ursprungliga numret, men vissa beräkningar är snabbare modulo ett mindre antal.

Begränsningar

Denna metod, som noterats ovan, är mycket effektiv för tal av formen r e ± s , där r och s är relativt små. Det är också effektivt för tal som kan representeras som ett polynom med små koefficienter. Faktum är att den speciella nummerfältsållmetoden sållar för två nummerfält. Metodens effektivitet är starkt beroende av storleken på vissa element inom dessa områden. Om ett tal kan representeras som ett polynom med små koefficienter är talen som beräknas mycket mindre än de tal som man har att göra med om ett sådant polynom inte finns.

Se även

Allmänt nummerfältsållmetod

Anteckningar

↑ Pomerance, Carl (december 1996), A Tale of Two Sieves , Notices of the AMS vol 43 (12): 1473–1485 , < http://www.ams.org/notices/199612/pomerance.pdf > Arkiverad kopia daterad 11 november 2020 på Wayback Machine
↑ Vasilenko, O.N. (2003), Talteoretiska kryptografialgoritmer , sid. 93-107 , < http://www.ict.edu.ru/ft/002416/book.pdf > Arkiverad 27 januari 2007 på Wayback Machine
↑ Pollard, JM (1988), Faktorering med kubiktal
↑ Franke, Jens Installationsanteckningar för ggnfs-lasieve4 . MIT Massachusetts Institute of Technology. Hämtad 4 december 2011. Arkiverad från originalet 5 september 2012. (obestämd)

Litteratur

Ishmukhametov, Sh.T. (2011), Faktoriseringsmetoder för naturliga tal , sid. 145-175 , < http://window.edu.ru/window_catalog/files/r73980/Monograph_ishm.pdf > (länk ej tillgänglig)
Byrnes, Steven (18 maj 2005), The Number Field Sieve , Math 129 , < http://modular.fas.harvard.edu/129-05/final_papers/Steve_Byrnes.pdf > . Hämtad 4 december 2011. Arkiverad 20 september 2006 på Wayback Machine
Lenstra, A.K .; Lenstra, HW, Jr. ; Manasse, MS & Pollard, JM (1993), The Factorization of the Ninth Fermat Number , Mathematics of Computation vol. 61 (203): 319–349, doi : 10.1090/S0025-5718-1993-1182953-4 , http: //www.std.org/~msm/common/f9paper.ps > Arkiverad 4 februari 2012 på Wayback Machine
Lenstra, A.K. & Lenstra, HW, Jr., red. (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). — Vol 1: 105–124

Länkar

NFS@Home