Faktorizace celého čísla - Integer factorization - Wikipedia

Nevyřešený problém v informatice: Lze celočíselnou faktorizaci vyřešit v polynomiálním čase na klasickém počítači? (více nevyřešených problémů v informatice)

v teorie čísel, celočíselná faktorizace je rozklad a složené číslo do produktu menších celých čísel. Pokud tyto faktory jsou dále omezeny na prvočísla, proces se nazývá Prvočíselný rozklad.

Když jsou čísla dostatečně velká, neúčinná, nekvantové celé číslo faktorizace algoritmus je známo. V roce 2019 započítali Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé a Paul Zimmermann 240místné číslo (RSA-240 ) využívající přibližně 900 jádrových let výpočetního výkonu.^[1] Vědci odhadli, že 1024bitový modul RSA bude trvat asi 500krát déle.^[2] Nebylo však prokázáno, že neexistuje žádný efektivní algoritmus. Předpokládaná obtížnost tohoto problému je jádrem široce používaných algoritmů v kryptografie jako RSA. Mnoho oblastí matematika a počítačová věda byly přivedeny k řešení problému, včetně eliptické křivky, algebraická teorie čísel, a kvantové výpočty.

Ne všechna čísla dané délky jsou stejně obtížná. Nejtěžší případy těchto problémů (pro aktuálně známé techniky) jsou semiprimes, součin dvou prvočísel. Když jsou oba velké, například více než dva tisíce bity dlouhé, náhodně vybrané a přibližně stejné velikosti (ale ne příliš blízko, například aby se zabránilo efektivní faktorizaci pomocí Fermatova faktorizační metoda ), dokonce i nejrychlejší algoritmy primární faktorizace na nejrychlejších počítačích může trvat dost času, aby bylo hledání nepraktické; to znamená, jak se zvyšuje počet číslic připravovaných prvočísel, drasticky se zvyšuje počet operací potřebných k provedení faktorizace na jakémkoli počítači.

Mnoho kryptografických protokolů je založeno na obtížnosti faktoringu velkých složených celých čísel nebo souvisejícím problému - například Problém RSA. Algoritmus, který efektivně ovlivňuje libovolné celé číslo, by se vykreslil RSA -na základě veřejný klíč kryptografie nejistá.

Prime rozklad

Prime rozklad n = 864 jako 2⁵ × 3³

Podle základní teorém aritmetiky, každé kladné celé číslo má jedinečný Prvočíselný rozklad. (Podle konvence je 1 prázdný produkt.) Testování zda celé číslo je prvočíslo, lze provést v polynomiální čas například Test prvosti AKS. Jsou-li však složené, polynomiální časové testy neposkytují žádný pohled na to, jak faktory získat.

Vzhledem k obecnému algoritmu pro celočíselnou faktorizaci lze do její složky započítat jakékoli celé číslo hlavní faktory opakovanou aplikací tohoto algoritmu. Situace je komplikovanější u speciálních faktorizačních algoritmů, jejichž výhody nemusí být realizovány stejně dobře, nebo dokonce vůbec, u faktorů produkovaných během rozkladu. Například pokud n = 171 × str × q kde str < q jsou velmi velká prvočísla, zkušební rozdělení rychle vytvoří faktory 3 a 19, ale vezme str divize najít další faktor. Jako kontrastní příklad, pokud n je produktem prvočísel 13729, 1372933 a 18848997161, kde 13729 × 1372933 = 18848997157, Fermatova faktorizační metoda bude začínat A = ⌈√n⌉ = 18848997159 který okamžitě dává b = √A² − n = √4 = 2 a tedy i faktory A − b = 18848997157 a A + b = 18848997161. I když jsou snadno rozpoznatelné jako složené a primární, Fermatova metoda bude trvat mnohem déle, než se bude skládat číslo, protože počáteční hodnota ⌈√18848997157⌉ = 137292 pro A není zdaleka 1372933.

Současný stav techniky

Mezi b-bitová čísla, nejobtížnější je v praxi při použití stávajících algoritmů zohlednit ta, která jsou produkty dvou prvočísel podobné velikosti. Z tohoto důvodu se jedná o celá čísla použitá v kryptografických aplikacích. Největší taková poloprima dosud zapracovaná byla RSA-250, 829bitové číslo s 250 desetinnými místy, v únoru 2020. Celková doba výpočtu byla zhruba 2700 jádrových let výpočtu pomocí Intel Xeon Zlatá 6130 na 2,1 GHz. Stejně jako všechny nedávné záznamy o faktorizaci byla i tato faktorizace dokončena vysoce optimalizovanou implementací síto obecného čísla běžet na stovkách strojů.

Obtížnost a složitost

Ne algoritmus byla zveřejněna, která dokáže započítat všechna celá čísla polynomiální čas, to znamená, že může činit a b-bitové číslo n včas Ó (b^k) pro nějakou konstantu k. Existence ani neexistence takových algoritmů nebyla prokázána, ale obecně existuje podezření, že neexistují, a proto problém není ve třídě P.^[3][4] Problém je jasně ve třídě NP, ale obecně se předpokládá, že tomu tak není NP-kompletní, i když to nebylo prokázáno.^[5]

Jsou publikovány algoritmy, které jsou rychlejší než O ((1 +ε)^b) pro všechny pozitivní ε, to znamená, subexponenciální. Publikovaný algoritmus s nejlepší asymptotickou dobou běhu^{[když? ]} je síto s obecným číselným polem (GNFS ), běží na a b-bitové číslo n včas:^{[je zapotřebí objasnění ]}

${ displaystyle exp left ( left ({ sqrt [{3}] { frac {64} {9}}} + o (1) right) ( ln n) ^ { frac {1} {3}} ( ln ln n) ^ { frac {2} {3}} vpravo).}$

Pro současné počítače je GNFS nejlépe publikovaným algoritmem pro velké počítače n (více než přibližně 400 bitů). Pro kvantový počítač, nicméně, Peter Shor objevil v roce 1994 algoritmus, který jej řeší v polynomiálním čase. To bude mít významné důsledky pro kryptografii, pokud se kvantový výpočet stane škálovatelným. Shorův algoritmus trvá jen Ó(b³) čas a O (b) místo zapnuto b- počet bitů. V roce 2001 byl Shorův algoritmus poprvé implementován pomocí NMR techniky na molekulách, které poskytují 7 qubitů.^[6]

Není přesně známo, které třídy složitosti obsahují rozhodovací verze problému celočíselné faktorizace (to znamená: dělá n mají faktor menší než k?). Je známo, že je v obou NP a co-NP, což znamená, že odpovědi „ano“ i „ne“ lze ověřit v polynomiálním čase. Odpověď „ano“ lze potvrdit vystavením faktorizace n = d(n/d) s d ≤ m. Odpověď „ne“ lze potvrdit vystavením faktorizace n do odlišných prvočísel, všechna větší než m; lze ověřit jejich primitivitu pomocí Test prvosti AKS a poté je znásobte n. The základní teorém aritmetiky zaručuje, že bude přijat pouze jeden možný řetězec rostoucích prvočísel, což ukazuje, že problém je v obou NAHORU a co-UP.^[7] Je známo, že je v BQP kvůli Shorovu algoritmu.

Předpokládá se, že problém je mimo všechny tři třídy složitosti P, NP-úplný a co-NP-kompletní. Je tedy kandidátem na NP-střední třída složitosti. Pokud by bylo možné prokázat, že je buď NP-úplný, nebo co-NP-úplný, znamenalo by to NP = co-NP, což je velmi překvapivý výsledek, a proto se obecně předpokládá, že celočíselná faktorizace je mimo obě tyto třídy. Mnoho lidí se pokusilo najít klasické algoritmy polynomiálního času a selhalo, a proto je široce podezření, že jsou mimo P.

Naproti tomu rozhodovací problém „Je n složené číslo? “(nebo ekvivalentně:„ Je n prvočíslo? ") se zdá být mnohem snazší než problém se specifikací faktorů n. Složený / primární problém lze vyřešit v polynomiálním čase (v počtu b číslic n) s Test prvosti AKS. Kromě toho existuje několik pravděpodobnostní algoritmy který může v praxi velmi rychle otestovat primitivnost, pokud je člověk ochoten akceptovat mizivě malou možnost chyby. Snadnost testování primality je klíčovou součástí RSA algoritmus, protože pro začátek je nutné najít velká prvočísla.

Faktoringové algoritmy

Speciální účel

Doba provozu speciálního factoringového algoritmu závisí na vlastnostech čísla, které má být faktorováno, nebo na jednom z jeho neznámých faktorů: velikost, speciální forma atd. Parametry, které určují dobu běhu, se u jednotlivých algoritmů liší.

Důležitou podtřídou speciálních factoringových algoritmů je Kategorie 1 nebo První kategorie algoritmy, jejichž doba běhu závisí na velikosti nejmenšího prime faktoru. Vzhledem k celému číslu neznámé formy se tyto metody obvykle používají před obecnými metodami k odstranění malých faktorů.^[8] Například naivní zkušební rozdělení je algoritmus kategorie 1.

• Zkušební rozdělení
• Faktorizace kola
• Pollardův rho algoritmus
• Algoritmy algebraické skupiny faktorizace, mezi nimiž jsou Pollard str - 1 algoritmus, Williamsova str + 1 algoritmus, a Faktorizace eliptické křivky Lenstra
• Fermatova faktorizační metoda
• Eulerova faktorizační metoda
• Speciální sítové pole

Univerzální

Univerzální factoringový algoritmus, známý také jako a Kategorie 2, Druhá kategorienebo Kraitchik rodina algoritmus,^[8] má dobu chodu, která závisí výhradně na velikosti celého čísla, které má být zohledněno. Toto je typ algoritmu použitého k výpočtu faktoru Čísla RSA. Většina factoringových algoritmů pro všeobecné účely je založena na shoda čtverců metoda.

• Dixonův algoritmus
• Pokračující zlomková faktorizace (CFRAC)
• Kvadratické síto
• Racionální síto
• Síto obecného čísla
• Shanksův čtverec formuje faktorizaci (SQUFOF)

Jiné pozoruhodné algoritmy

• Shorův algoritmus, pro kvantové počítače

Heuristická doba běhu

V teorii čísel existuje mnoho celočíselných factoringových algoritmů, které heuristicky očekávali provozní doba

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

v malý-o a L-notace Některé příklady těchto algoritmů jsou metoda eliptické křivky a kvadratické síto.Dalším takovým algoritmem je metoda třídních skupinových vztahů navrhl Schnorr,^[9] Seysen,^[10] a Lenstra,^[11] což se ukázalo pouze za předpokladu, že nebylo prokázáno Zobecněná Riemannova hypotéza (GRH).

Přísná doba provozu

Pravděpodobnostní algoritmus Schnorr – Seysen – Lenstra byl důkladně prokázán Lenstrou a Pomerance^[12] očekávat dobu chodu ${ displaystyle L_ {n} left [{ tfrac {1} {2}}, 1 + o (1) right]}$ tím, že nahradí předpoklad GRH použitím multiplikátorů. Algoritmus používá skupina tříd pozitivní binární kvadratické formy z diskriminující Δ označeno G_Δ.G_Δ je sada trojic celých čísel (A, b, C) ve kterých jsou tato celá čísla relativní prvočísla.

Algoritmus Schnorr – Seysen – Lenstra

Dáno celé číslo n to bude zohledněno, kde n je liché kladné celé číslo větší než určitá konstanta. V tomto factoringovém algoritmu je diskriminační Δ zvolen jako násobek n, Δ = -dn, kde d je nějaký pozitivní multiplikátor. Algoritmus to očekává pro jednu d existuje dost hladký formuláře v G_Δ. Lenstra a Pomerance ukazují, že volba d lze omezit na malou sadu, aby byl zaručen hladký výsledek.

Označit podle P_Δ sada všech prvočísel q s Symbol Kronecker ${ displaystyle left ({ tfrac { Delta} {q}} right) = 1}$. Vytvořením sady generátory z G_Δ a prvočísla F_q z G_Δ s q v P_Δ posloupnost vztahů mezi sadou generátorů a F_q jsou vyráběny. Velikost q lze omezit ${ displaystyle c_ {0} ( log | Delta |) ^ {2}}$ pro nějakou konstantu ${ displaystyle c_ {0}}$.

Vztah, který bude použit, je vztah mezi součinem sil, který se rovná neutrální prvek z G_Δ. Tyto vztahy budou použity k vytvoření takzvané nejednoznačné formy G_Δ, což je prvek G_Δ řádového dělení 2. Výpočtem odpovídající faktorizace Δ a získáním a gcd, tato nejednoznačná forma poskytuje úplnou primární faktorizaci n. Tento algoritmus má tyto hlavní kroky:

Nechat n být číslo, které má být zohledněno.

1. Nechť Δ je záporné celé číslo s Δ = -dn, kde d je multiplikátor a Δ je negativní diskriminátor nějaké kvadratické formy.
2. Vezměte t první připraví ${ displaystyle p_ {1} = 2, p_ {2} = 3, p_ {3} = 5, tečky, p_ {t}}$, pro některé ${ displaystyle t in { mathbb {N}}}$.
3. Nechat ${ displaystyle f_ {q}}$ být náhodná prime forma G_Δ s ${ displaystyle left ({ tfrac { Delta} {q}} right) = 1}$.
4. Najděte generátorovou sadu X z G_Δ
5. Sbírejte posloupnost vztahů mezi množinou X a {F_q : q ∈ P_Δ} uspokojující: ${ displaystyle left ( prod _ {x in X _ {}} x ^ {r (x)} right). left ( prod _ {q in P _ { Delta}} f_ {q} ^ {t (q)} vpravo) = 1}$
6. Vytvořte nejednoznačnou formu ${ displaystyle (a, b, c)}$ to je prvek F ∈ G_Δ řádu dělení 2 pro získání coprime faktorizace největšího lichého dělitele Δ, ve kterém ${ displaystyle Delta = -4ac { text {nebo}} a (a-4c) { text {nebo}} (b-2a) (b + 2a)}$
7. Pokud dvojznačná forma poskytuje faktorizaci n pak přestaňte, jinak najděte jinou nejednoznačnou formu až do faktorizace n je nalezeno. Aby se zabránilo generování zbytečných nejednoznačných forem, vybudujte 2-Sylow skupina Sll₂(Δ) z G(Δ).

Chcete-li získat algoritmus pro factoring libovolného kladného celého čísla, je nutné přidat k tomuto algoritmu několik kroků, například zkušební dělení a Jacobiho součet.

Předpokládaná doba provozu

Uvedený algoritmus je a pravděpodobnostní algoritmus jak to dělá náhodná rozhodnutí. Očekávaná doba provozu je maximálně ${ displaystyle L_ {n} left [{ tfrac {1} {2}}, 1 + o (1) right]}$.^[12]

Viz také

• Bachův algoritmus pro generování náhodných čísel s jejich faktorizací
• Kanonické vyjádření kladného celého čísla
• Faktorizace
• Multiplikativní oddíl
• Oddíl (teorie čísel) - způsob zápisu čísla jako součet kladných celých čísel.

Poznámky

Reference

• Richard Crandall a Carl Pomerance (2001). Prvočísla: Výpočetní perspektiva. Springer. ISBN  0-387-94777-9. Kapitola 5: Algoritmy exponenciálního faktoringu, s. 191–226. Kapitola 6: Algoritmy subexponenciálního faktoringu, s. 227–284. Část 7.4: Metoda eliptické křivky, s. 301–313.
• Donald Knuth. Umění počítačového programování, Díl 2: Seminumerické algoritmy, Třetí edice. Addison-Wesley, 1997. ISBN  0-201-89684-2. Oddíl 4.5.4: Faktorování do prvočísel, s. 379–417.
• Samuel S. Wagstaff, Jr. (2013). Radost z faktoringu. Providence, RI: American Mathematical Society. ISBN  978-1-4704-1048-3..
• Warren Jr., Henry S. (2013). Hacker's Delight (2. vyd.). Addison Wesley - Pearson Education, Inc. ISBN  978-0-321-84268-8.

externí odkazy

• msieve - SIQS a NFS - pomohl dokončit některé z největších známých veřejných faktorizací
• Richard P. Brent, „Nedávný pokrok a vyhlídky na celočíselné faktorizační algoritmy“, Výpočetní technika a kombinatorika ", 2000, s. 3–22. stažení
• Manindra Agrawal „Neeraj Kayal, Nitin Saxena,„ PRIMES je v P. “ Annals of Mathematics 160 (2): 781-793 (2004). Verze PDF ze srpna 2005
• Eric W. Weisstein, „RSA-640 Factored“ Titulní novinky MathWorld, 8. listopadu 2005