Faktorizace celého čísla - Integer factorization

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 teorii čísel , celé číslo faktorizace je rozklad složené číslo do produktu menších celých čísel. Pokud jsou tyto faktory dále omezeny na prvočísla , tento proces se nazývá primární faktorizace .

Když jsou čísla dostatečně velká, není znám žádný účinný nekvantový celočíselný faktorizační algoritmus . Nebylo však prokázáno, že neexistuje účinný algoritmus. Předpokládaná obtížnost tohoto problému je jádrem široce používaných algoritmů v kryptografii , jako je RSA . Na problém se zaměřilo mnoho oblastí matematiky a informatiky , včetně eliptických křivek , teorie algebraických čísel a kvantové výpočetní techniky .

V roce 2019 Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé a Paul Zimmermann založili 240místné (795bitové) číslo ( RSA-240 ) využívající přibližně 900 jaderných let výpočetního výkonu. Vědci odhadovali, že 1024bitový modul RSA bude trvat asi 500krát déle.

Ne všechna čísla dané délky je stejně těžké rozeznat. Nejtěžšími příklady těchto problémů (pro v současnosti známé techniky) jsou semiprimes , součin dvou prvočísel. Když jsou oba velké, například více než dva tisíce bitů dlouhé, náhodně vybrané a přibližně stejné velikosti (ale ne příliš blízko, například aby se zabránilo efektivní faktorizaci Fermatovou faktorizační metodou ), dokonce i nejrychlejší primární faktorizační algoritmy na nejrychlejším počítačům může trvat dost času, než bude vyhledávání nepraktické; to znamená, že jak se zvyšuje počet číslic prvočísel, které jsou faktorizovány, 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ího problému - například problému RSA . Algoritmus, který efektivně zohledňuje libovolné celé číslo, by způsobil nejistotu kryptografie veřejného klíče na bázi RSA .

Primární rozklad

Rozklad n = 864 jako 2 5 × 3 3

Podle základní věty o aritmetice má každé kladné celé číslo jedinečnou primární faktorizaci . (Podle konvence je 1 prázdný součin .) Testování, zda je celé číslo prvočíslo, lze provést v polynomiálním čase , například testem primality AKS . Pokud jsou však složené, polynomiální časové testy neposkytují žádný pohled na to, jak tyto faktory získat.

Vzhledem k obecnému algoritmu pro celočíselnou faktorizaci lze libovolné celé číslo započítat do jeho primárních součinitelů opakováním aplikace tohoto algoritmu. Složitější je situace u faktorizačních algoritmů pro speciální účely, jejichž výhody nemusí být s faktory vytvořenými během rozkladu realizovány stejně dobře nebo dokonce vůbec. Například pokud n = 171 × p × q, kde p < q jsou velmi velké prvočísla, zkušební dělení rychle vytvoří faktory 3 a 19, ale bude potřebovat dělení p, aby našlo další faktor. Jako kontrastní příklad platí, že pokud n je součin prvočísel 13729, 1372933 a 18848997161, kde 13729 × 1372933 = 18848997157 , začne Fermatova metoda faktorizace, která okamžitě poskytne výtěžky, a tedy faktory a - b = 18848997157 a a + b = 18848997161 . Zatímco tito jsou snadno rozpoznatelné jako kompozitní a prime respektive bude Fermat metoda trvat mnohem déle, než faktor složený číslo, protože výchozí hodnota pro není zdaleka 1372933.

Současný stav techniky

Mezi b -bitovými čísly jsou v praxi s využitím stávajících algoritmů nejobtížněji zohlednit ty, které jsou součinem dvou prvočísel podobné velikosti. Z tohoto důvodu se jedná o celá čísla používaná v kryptografických aplikacích. Největší dosud takto zohledněný semiprime byl RSA-250 , 829bitové číslo s 250 desetinnými číslicemi, v únoru 2020. Celková doba výpočtu byla zhruba 2700 jaderných let výpočetní techniky využívající Intel Xeon Gold 6130 na 2,1 GHz. Stejně jako všechny nedávné záznamy o faktorizaci byla i tato faktorizace dokončena vysoce optimalizovanou implementací obecného sítového pole provozovaného na stovkách strojů.

Obtížnost a složitost

Nebyl publikován žádný algoritmus, který by dokázal spočítat všechna celá čísla v polynomiálním čase , to znamená, že by pro nějakou konstantu k mohl činit b -bitové číslo n v čase O ( b k ) . Nebyla prokázána existence ani neexistence takových algoritmů, ale obecně se předpokládá, že neexistují, a proto problém není ve třídě P. Problém je jasně ve třídě NP, ale obecně se předpokládá, že není NP-kompletní , i když to nebylo prokázáno.

Jsou publikovány algoritmy, které jsou rychlejší než O ((1 +  ε ) b ) pro všechna kladná e , tj . Subexponenciální . Jak 2021-03-12, algoritmus s nejlepší teoretickou asymptotickou dobou běhu je obecné síto číselného pole ( GNFS ), poprvé publikované v roce 1993, běžící na b- bitovém čísle n v čase:

Pro současné počítače je GNFS nejlépe publikovaným algoritmem pro velké n (více než asi 400 bitů). Pro kvantový počítač však Peter Shor objevil v roce 1994 algoritmus, který ho řeší v polynomiálním čase. To bude mít významné důsledky pro kryptografii, pokud bude kvantový výpočet škálovatelný. Algoritmus Shor trvá na vstupech s b -bitovým číslem pouze čas O ( b 3 ) a prostor O ( b ) . V roce 2001 byl Shorův algoritmus poprvé implementován pomocí technik NMR na molekulách, které poskytují 7 qubitů.

Není přesně známo, které třídy složitosti obsahují rozhodovací verzi problému celočíselné faktorizace (to znamená: má n faktor menší než k ?). Je známo, že je v NP i co-NP , což znamená, že odpovědi „ano“ i „ne“ lze ověřit v polynomiálním čase. Odpověď „ano“ lze certifikovat vystavením faktorizace n = d ( n / d ) s dk . Odpověď „ne“ lze certifikovat vystavením faktorizace n na odlišná prvočísla, všechna větší než k ; je možné ověřit jejich primalitu pomocí testu primality AKS a poté je znásobit a získat n . Základní věta aritmetiky zaručuje, že je tam jen jeden možný řetězec zvyšujících prvočísel, které budou přijaty, což ukazuje, že problém je v obou UP a co-UP. 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-Complete a co-NP-Complete . Je tedy kandidátem na třídu NP-střední 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 pro něj klasické polynomiální časové algoritmy a neuspěli, a proto je obecně podezření, že se nacházejí mimo P.

Naproti tomu problém s rozhodováním „Je n složené číslo?“ (nebo ekvivalentně: „Je n prvočíslo?“) se zdá být mnohem jednodušší než problém specifikování faktorů n . Kompozitní/prvočíselný problém lze vyřešit v polynomiálním čase (v počtu b číslic n ) pomocí testu primality AKS . Kromě toho existuje několik pravděpodobnostních algoritmů, které dokážou v praxi velmi rychle otestovat primalitu, pokud je člověk ochoten přijmout mizivě malou možnost chyby. Snadnost testování primality je zásadní součástí algoritmu RSA , protože je nutné pro začátek najít velká prvočísla.

Faktorové algoritmy

Speciální účel

Doba běhu algoritmu faktoringu pro speciální účely závisí na vlastnostech čísla, které má být zohledněno, nebo na jednom z jeho neznámých faktorů: velikost, speciální forma atd. Parametry, které určují dobu běhu, se mezi algoritmy liší.

Důležitou podtřídou účelových faktoringových algoritmů jsou algoritmy kategorie 1 nebo první kategorie , jejichž doba běhu závisí na velikosti nejmenšího prvotního 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ů. Například naivní zkušební dělení je algoritmus kategorie 1.

Všeobecné použití

Algoritmus faktoringu pro obecné účely, známý také jako algoritmus kategorie 2 , druhé kategorie nebo rodiny Kraitchiků , má dobu běhu, která závisí výhradně na velikosti celého čísla, které má být zohledněno. Toto je typ algoritmu, který se používá k faktorování čísel RSA . Většina faktorových algoritmů pro obecné účely je založena na metodě kongruence čtverců .

Jiné pozoruhodné algoritmy

Heuristická doba běhu

V teorii čísel existuje mnoho celočíselných faktoringových algoritmů, které heuristicky očekávaly dobu běhu

v malém o a L-notaci . 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ů navržená Schnorrem, Seysenem a Lenstrem, kterou dokázali pouze za předpokladu neprokázané generalizované Riemannovy hypotézy (GRH) .

Rigorózní doba běhu

Lenstra a Pomerance důsledně prokázaly pravděpodobnostní algoritmus Schnorr – Seysen – Lenstra tím, že očekávaly dobu běhu nahrazením předpokladu GRH použitím multiplikátorů. Algoritmus využívá třídy skupiny pozitivních binární kvadratické formy s diskriminační delta označených G , delta . G Δ je množina trojic celých čísel ( a , b , c ), ve kterých jsou tato celá čísla relativní prvočísla.

Algoritmus Schnorr – Seysen – Lenstra

Vzhledem k celému číslu n, které bude započítáno, kde n je liché kladné celé číslo větší než určitá konstanta. V tomto faktoringovém algoritmu je diskriminant Δ zvolen jako násobek n , Δ = - dn , kde d je nějaký pozitivní multiplikátor. Algoritmus očekává, že na jedno d existuje v G Δ dostatek hladkých forem . Lenstra a Pomerance ukazují, že výběr d lze omezit na malou sadu, aby byl zaručen hladký výsledek.

Označme P ó množina všech prvočísel q s Kronecker symbolem . Výstavbou sadu generátorů o G , delta a hlavních forem f q z G delta s Q na P , delta sekvenci vztahů mezi souborem generátorů a f q jsou vyráběny. Velikost q může být ohraničena nějakou konstantou .

Vztah, který bude použit, je vztah mezi produktem sil, které se rovná neutrální prvek z G delta . Tyto vztahy budou použity ke konstrukci takzvané nejednoznačné formy G Δ , což je prvek G Δ řádu dělícího 2. Výpočtem odpovídající faktorizace Δ a přijetím gcd poskytuje tato nejednoznačná forma úplnou primární faktorizaci z n . Tento algoritmus má tyto hlavní kroky:

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

  1. Nechť Δ je záporné celé číslo s Δ = - dn , kde d je multiplikátor a Δ je záporný diskriminátor nějaké kvadratické formy.
  2. Přijmou t první prvočísla , pro některé .
  3. Nechť je náhodná primární forma G Δ s .
  4. Najít set generování X a G delta
  5. Shromážděte posloupnost vztahů mezi sadou X a { f q  : qP Δ } splňující:
  6. Sestrojte nejednoznačnou formu, která je prvkem fG Δ řádu dělícího 2, abyste získali coprime faktorizaci největšího lichého dělitle Δ, ve kterém
  7. Pokud nejednoznačná forma poskytuje faktorizaci n, zastavte se, v opačném případě najděte jinou nejednoznačnou formu, dokud nebude nalezena faktorizace n . Aby se zabránilo generování zbytečných nejednoznačných forem, vytvořte 2- Sylowovu skupinu Sll 2 (Δ) z G (Δ).

Chcete -li získat algoritmus pro rozdělování kladných celých čísel, je nutné k tomuto algoritmu přidat několik kroků, jako je zkušební dělení a Jacobiův součet .

Očekávaná doba chodu

Algoritmus, jak je uvedeno, je pravděpodobnostní algoritmus, protože dělá náhodné volby. Jeho předpokládaná doba běhu je maximálně .

Viz také

Poznámky

Reference

externí odkazy