Heltalsfaktorisering

"Prime decomposition" omdirigerar här. För primtoppsupplösningssatsen för 3-grenrör, se Primerupplösning (3-grenrör) .

Olöst problem inom datavetenskap :

Kan heltalsfaktorisering lösas i polynomtid på en klassisk dator?

(fler olösta problem inom datavetenskap)

I talteorin är heltalsfaktorisering nedbrytningen, när det är möjligt, av ett positivt heltal till en produkt av mindre heltal. Om faktorerna begränsas ytterligare till att vara primtal kallas processen primtalsfaktorisering och inkluderar testet om det givna heltal är primtal (i detta fall har man en "produkt" av en enda faktor).

När siffrorna är tillräckligt stora är ingen effektiv icke - kvantheltalsfaktoriseringsalgoritm känd . Det är dock inte bevisat att en sådan algoritm inte existerar. Den förmodade svårigheten med detta problem är viktig för de algoritmer som används i kryptografi , såsom RSA public-key-kryptering och RSA digital signatur . Många områden av matematik och datavetenskap har kommit med att uthärda problemet, inklusive elliptiska kurvor , algebraisk talteori och kvantberäkning .

Under 2019 räknade Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé och Paul Zimmermann ett 240-siffrigt (795-bitars) nummer ( RSA-240 ) med hjälp av cirka 900 kärnår av datorkraft. Forskarna uppskattade att en 1024-bitars RSA-modul skulle ta cirka 500 gånger så lång tid.

Alla tal av en given längd är inte lika svåra att faktorisera. De svåraste fallen av dessa problem (för för närvarande kända tekniker) är semiprimtal , produkten av två primtal. När de båda är stora, till exempel mer än tvåtusen bitar långa, slumpmässigt valda och ungefär lika stora (men inte för nära, till exempel för att undvika effektiv faktorisering med Fermats faktoriseringsmetod ) , kan även de snabbaste primtalsfaktoriseringsalgoritmerna på snabbaste datorer kan ta tillräckligt med tid för att göra sökningen opraktisk; det vill säga, när antalet siffror i det heltal som faktoriseras ökar, ökar antalet operationer som krävs för att utföra faktoriseringen på vilken dator som helst drastiskt.

Många kryptografiska protokoll är baserade på svårigheten att faktorisera stora sammansatta heltal eller ett relaterat problem – till exempel RSA-problemet . En algoritm som effektivt tar hänsyn till ett godtyckligt heltal skulle göra RSA -baserad kryptografi med publik nyckel osäker.

Prime sönderdelning

Grundsönderdelning av n = 864 som 2 ⁵ × 3 ³

Enligt aritmetikens grundsats har varje positivt heltal en unik primtalsfaktorisering . (I enlighet med konventionen är 1 den tomma produkten .) Att testa om heltal är primtal kan göras i polynomtid , till exempel med AKS-primalitetstestet . Om de är sammansatta ger däremot polynomtidstesten ingen insikt i hur man skaffar faktorerna.

Givet en allmän algoritm för heltalsfaktorisering, kan vilket heltal som helst faktoriseras i dess ingående primtalsfaktorer genom upprepad tillämpning av denna algoritm. Situationen är mer komplicerad med speciella faktoriseringsalgoritmer, vars fördelar kanske inte realiseras lika bra eller ens alls med de faktorer som produceras under nedbrytningen. Till exempel, om n = 171 × p × q där p < q är mycket stora primtal, kommer provdelning snabbt att producera faktorerna 3 och 19 men kommer att ta p divisioner för att hitta nästa faktor. Som ett kontrasterande exempel, om n är produkten av primtal 13729, 1372933 och 18848997161, där $1 8 ft ⌈ n 1 ⌉ 15 ft \sqrt {n }}\right\rceil =18848997159}$ × 1372933 = 18848997157 , Fermats faktoriseringsmetod att börja med vilket omedelbart ger ${\textstyle b={\sqrt {a^{2}-n}}={\sqrt {4}}= 2b}$ och därav faktorerna a − b = 18848997157 och a + b = 18848997161 . Även om dessa lätt känns igen som sammansatta respektive primtal, kommer Fermats metod att ta mycket längre tid att faktorisera det sammansatta talet eftersom startvärdet för ⌈ 18848997157 ⌉ = $left\lceil {\sqrt {18848997157}}\,\right \rceil =137292}$ för a är inte i närheten av 1372933.

Nuvarande toppmoderna

Se även: Heltalsfaktoriseringsposter

Bland b -bittalen är de som är svårast att faktorisera i praktiken med hjälp av befintliga algoritmer de som är produkter av två primtal av liknande storlek. Av denna anledning är dessa heltal som används i kryptografiska applikationer. Den största sådana semiprime som hittills tagits i beaktande var RSA-250 , ett 829-bitars nummer med 250 decimalsiffror, i februari 2020. Den totala beräkningstiden var ungefär 2700 kärnår av datoranvändning med Intel Xeon Gold 6130 vid 2,1 GHz. Liksom alla nya faktoriseringsposter, fullbordades denna faktorisering med en mycket optimerad implementering av den allmänna nummerfältssikten som kördes på hundratals maskiner.

Svårighet och komplexitet

Ingen algoritm har publicerats som kan faktorisera alla heltal i polynomtid , det vill säga som kan faktorisera ett b -bitars nummer n i tiden O ( b ^k ) för någon konstant k . Varken existensen eller icke-existensen av sådana algoritmer har bevisats, men det är allmänt misstänkt att de inte existerar och därmed att problemet inte är i klass P. Problemet är helt klart i klass NP, men det är allmänt misstänkt att det är inte NP-komplett , även om detta inte har bevisats.

Det finns publicerade algoritmer som är snabbare än O((1 + ε ) ^b ) för alla positiva ε , det vill säga subexponentiella . Från och med 2022 är algoritmen med bästa teoretiska asymptotiska körtid den allmänna talfältssikten (GNFS), först publicerad 1993, som körs på ett b -bit nummer n i tid:

$\exp \left(\left({\sqrt[{3}]{\frac {64}{9}}}+o(1)\right)(\ln n)^{\frac {1} {3}}(\ln \ln n)^{\frac {2}{3}}\höger).$

För nuvarande datorer är GNFS den bäst publicerade algoritmen för stora n (mer än cirka 400 bitar). För en kvantdator upptäckte Peter Shor en algoritm 1994 som löser det i polynomtid . Detta kommer att få betydande konsekvenser för kryptografi om kvantberäkningen blir skalbar. Shors algoritm tar endast O( b ³ ) tid och O( b ) utrymme på b -bitars nummerinmatningar. 2001 implementerades Shors algoritm för första gången genom att använda NMR- tekniker på molekyler som ger 7 qubits.

Det är inte känt exakt vilka komplexitetsklasser som innehåller beslutsversionen av heltalsfaktoriseringsproblemet (det vill säga: har n en faktor som är mindre än k ?). Det är känt att det finns i både NP och co-NP , vilket betyder att både "ja" och "nej"-svar kan verifieras i polynomtid. Ett svar på "ja" kan intygas genom att uppvisa en faktorisering n = d ( n / d ) med d ≤ k . Ett svar på "nej" kan intygas genom att uppvisa faktoriseringen av n till distinkta primtal, alla större än k ; man kan verifiera deras primalitet med AKS primalitetstestet och sedan multiplicera dem för att få n . Aritmetikens grundsats garanterar att det bara finns en möjlig sträng av ökande primtal som kommer att accepteras, vilket visar att problemet finns i både UP och co-UP. Det är känt att det finns i BQP på grund av Shors algoritm.

Problemet misstänks ligga utanför alla tre komplexitetsklasserna P, NP-komplett och co-NP-komplett . Det är därför en kandidat för NP- mellankomplexitetsklassen. Om det kunde bevisas vara antingen NP-komplett eller co-NP-komplett skulle detta innebära NP = co-NP, ett mycket överraskande resultat, och därför är heltalsfaktorisering allmänt misstänkt att ligga utanför båda dessa klasser.

Däremot beslutsproblemet "Är n ett sammansatt tal?" (eller motsvarande: "Är n ett primtal?") verkar vara mycket lättare än problemet med att specificera faktorer för n . Det sammansatta/primtalsproblemet kan lösas i polynomtid (i antalet b siffror i n ) med AKS-primalitetstestet . Dessutom finns det flera probabilistiska algoritmer som kan testa primatiteten mycket snabbt i praktiken om man är villig att acceptera en försvinnande liten möjlighet till fel. Lättheten att testa primat är en avgörande del av RSA -algoritmen, eftersom det är nödvändigt att hitta stora primtal till att börja med.

Faktoreringsalgoritmer

Speciell anledning

En factoringalgoritms körtid för specialändamål beror på egenskaperna hos talet som ska faktoriseras eller på någon av dess okända faktorer: storlek, speciell form, etc. Parametrarna som bestämmer körtiden varierar mellan algoritmerna.

En viktig underklass av factoringalgoritmer för speciella ändamål är kategori 1- eller förstakategorialgoritmerna , vars körtid beror på storleken på den minsta primfaktorn. Givet ett heltal av okänd form, används dessa metoder vanligtvis före generella metoder för att ta bort små faktorer. Till exempel är naiv provdelning en kategori 1-algoritm.

• Försöksuppdelning
• Hjulfaktorisering
• Pollards rho-algoritm , som har två gemensamma smaker för att identifiera gruppcykler : en av Floyd och en av Brent.
• Algebraiska gruppfaktoriseringsalgoritmer , bland vilka är Pollards p − 1 algoritm , Williams p + 1 algoritm och Lenstra elliptisk kurvfaktorisering
• Fermats faktoriseringsmetod
• Eulers faktoriseringsmetod
• Specialnummerfältsåll

Generell mening

En factoringalgoritm för allmänt ändamål, även känd som en kategori 2- , andra kategori- eller Kraitchik - familjealgoritm , har en körtid som enbart beror på storleken på det heltal som ska faktoriseras. Detta är den typ av algoritm som används för att faktorisera RSA-nummer . De flesta generella factoringalgoritmer är baserade på metoden kongruens av kvadrater .

• Dixons algoritm
• Fortsatt fraktionsfaktorisering (CFRAC)
• Kvadratisk sil
• Rationell såll
• Allmänt nummer fältsil
• Shanks's square forms factorization (SQUFOF)

Andra anmärkningsvärda algoritmer

• Shors algoritm , för kvantdatorer

Heuristisk gångtid

I talteorin finns det många heltalsfaktoreringsalgoritmer som heuristiskt sett har förväntad körtid

$L_{n}\left[{\tfrac {1 }{2}},1+o(1)\right]=e^{(1+o(1)){\sqrt {(\log n)(\log \log n)}}}$

i little-o och L-notation . Några exempel på dessa algoritmer är den elliptiska kurvmetoden och den kvadratiska sikten . En annan sådan algoritm är klassgruppsrelationsmetoden som föreslagits av Schnorr, Seysen och Lenstra, som de bevisade endast med antagande av den obevisade Generalized Riemann Hypothesis (GRH) .

Rigorös körtid

$L_{n}\left[{\tfrac {1} {2}},1+o(1)\right]$ att ha förväntat körtid genom att ersätta GRH-antagandet med användning av multiplikatorer. Algoritmen använder klassgruppen av positiva binära kvadratiska former av diskriminant Δ betecknad med G _Δ . G _Δ är mängden trippel av heltal ( a , b , c ) där dessa heltal är relativa primtal.

Schnorr–Seysen–Lenstra Algoritm

Givet ett heltal n som kommer att faktoriseras, där n är ett udda positivt heltal större än en viss konstant. I denna faktoriseringsalgoritm väljs diskriminanten Δ som en multipel av n , Δ = − dn , där d är någon positiv multiplikator. Algoritmen förväntar sig att det för en d finns tillräckligt med jämna former i G _Δ . Lenstra och Pomerance visar att valet av d kan begränsas till en liten uppsättning för att garantera jämnhetsresultatet.

Beteckna med P _Δ mängden av alla primtal q med Kronecker-symbolen $\left({\tfrac {\Delta }{q}}\right)=1$ . Genom att konstruera en uppsättning generatorer av G _Δ och primformerna f _q av G _Δ med q i P _Δ skapas en sekvens av relationer mellan uppsättningen generatorer och f _{q .} Storleken på q kan begränsas av $c_{0}(\log |\Delta |)^{2}$ för någon konstant $c_{0}$ .

Relationen som kommer att användas är en relation mellan produkten av potenser som är lika med det neutrala elementet av G _Δ . Dessa relationer kommer att användas för att konstruera en så kallad tvetydig form av G _Δ , som är ett element av G _Δ av ordningsdelning 2. Genom att beräkna motsvarande faktorisering av Δ och genom att ta en gcd , ger denna tvetydiga form den fullständiga primtalsfaktoriseringen av n . Denna algoritm har dessa huvudsteg:

Låt n vara talet som ska faktoriseras.

1. Låt Δ vara ett negativt heltal med Δ = − dn , där d är en multiplikator och Δ är den negativa diskriminanten av någon kvadratisk form.
2. Ta de första primtalen $p_{1}=2,p_{2}=3,p_{3}=5,\ldots ,p_{t}$ , för vissa $t\in {\mathbb {N} }$ .
3. Låt $f_{q}$ vara en slumpmässig primform av G _Δ med ${\textstyle \left({\frac {\Delta {q}}\right)=1}$ .
4. Hitta en genereringsmängd X av G _Δ
5. Samla en sekvens av relationer mellan mängden X och { f _q : q ∈ P _Δ } som uppfyller: ${\textstil \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _ {q\in P_{\Delta }}f_{q}^{t(q)}\right)=1}$
6. Konstruera en tvetydig form $(a,b,c)$ som är ett element f ∈ G _Δ av ordningen som delar 2 för att erhålla en coprime-faktorisering av den största udda divisorn av Δ där $\Delta =-4ac{\text{ eller }}a(a-4c){\text{ eller }}(b-2a)(b+2a)$
7. Om den tvetydiga formen ger en faktorisering av n , sluta, annars hitta en annan tvetydig form tills faktoriseringen av n hittas. För att förhindra att värdelösa tvetydiga former genereras, bygg upp 2-Sylow -gruppen Sll ₂ (Δ) av G (Δ).

För att erhålla en algoritm för att faktorisera ett positivt heltal är det nödvändigt att lägga till några steg till denna algoritm, såsom provdelning och Jacobis summatest .

Förväntad gångtid

Algoritmen som anges är en probabilistisk algoritm eftersom den gör slumpmässiga val. Dess förväntade körtid är som mest $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ .

Se även

• Aurifeuillean faktorisering
• Bachs algoritm för att generera slumptal med deras faktoriseringar
• Kanonisk representation av ett positivt heltal
• Faktorisering
• Multiplikativ partition
• $p$ -adic värdering
• Partition (talteori) – ett sätt att skriva ett tal som en summa av positiva heltal.

Anteckningar

•   Richard Crandall och Carl Pomerance (2001). Prime Numbers: A Computational Perspective . Springer. ISBN 0-387-94777-9 . Kapitel 5: Exponential Factoring Algorithms, s. 191–226. Kapitel 6: Subexponentiella faktoriseringsalgoritmer, s. 227–284. Avsnitt 7.4: Elliptisk kurvmetod, s. 301–313.
•   Donald Knuth . The Art of Computer Programming , Volym 2: Seminumerical Algorithms , tredje upplagan. Addison-Wesley, 1997. ISBN 0-201-89684-2 . Avsnitt 4.5.4: Factoring into Primes, s. 379–417.
•   Samuel S. Wagstaff Jr. (2013). Glädjen med att faktorisera . Providence, RI: American Mathematical Society. ISBN 978-1-4704-1048-3 . .
•   Warren, Henry S. Jr. (2013). Hacker's Delight (2 uppl.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8 .

externa länkar

• msieve - SIQS och NFS - har hjälpt till att slutföra några av de största kända offentliga faktoriseringarna
• Richard P. Brent, "Recent Progress and Prospects for Integer Factorization Algorithms", Computing and Combinatorics , 2000, s. 3–22. ladda ner
• Manindra Agrawal , Neeraj Kayal, Nitin Saxena, "PRIMES är i P." Annals of Mathematics 160(2): 781-793 (2004). Augusti 2005 version pdf
• Eric W. Weisstein, "RSA-640 Factored" MathWorld Headline News , 8 november 2005
• Dario Alperns heltalsfaktoriseringskalkylator - En webbapp för faktorisering av stora heltal