Dixonova faktorizační metoda - Dixons factorization method - Wikipedia
v teorie čísel, Dixonova faktorizační metoda (taky Dixonova metoda náhodných čtverců[1] nebo Dixonův algoritmus) je univerzální celočíselná faktorizace algoritmus; je to prototyp faktorová základna metoda. Na rozdíl od jiných metod faktorové báze má jeho běhová vazba přísný důkaz, který se nespoléhá na domněnky o vlastnostech hladkosti hodnot přijatých polynomem.
Algoritmus navrhl John D. Dixon, matematik v Carleton University, a byla zveřejněna v roce 1981.[2]
Základní myšlenka
Dixonova metoda je založena na nalezení a shoda čtverců modulo celé číslo N, které je určeno k faktoru. Fermatova faktorizační metoda najde takovou shodu výběrem náhodného nebo pseudonáhodné X hodnoty a doufat, že celé číslo X2 mod N je a perfektní čtverec (v celých číslech):
Například pokud N = 84923, (od 292 je první číslo větší než √N a počítání) 5052 mod 84923 je 256, čtverec 16. Takže (505 - 16) (505 + 16) = 0 mod 84923. Výpočet největší společný dělitel z 505 − 16 a N použitím Euklidův algoritmus dává 163, což je faktor N.
V praxi je výběr náhodný X hodnot bude trvat neprakticky dlouho, než se najde shoda čtverců, protože existují pouze √N čtverce menší než N.
Dixonova metoda nahrazuje podmínku „je druhou mocninou celého čísla“ mnohem slabší „má jen malé primární faktory“; například existuje 292 čtverců menších než 84923; 662 čísel menších než 84923, jejichž hlavní faktory jsou pouze 2,3,5 nebo 7; a 4767, jejichž hlavní faktory jsou všechny menší než 30. (Takovým číslům se říká B-hladký s ohledem na některé vázané B.)
Pokud existuje mnoho čísel jehož čtverce lze faktorizovat jako pro pevnou sadu malých prvočísel, lineární algebra modulo 2 na matici dá podmnožinu souboru jehož čtverce se spojí s produktem malých prvočísel k rovnoměrné síle - to je podmnožina jehož čtverce se množí na druhou mocninu (snad jiného) čísla mod N.
Metoda
Předpokládejme složené číslo N se započítává. Vázaný B je vybrán a faktorová základna je identifikován (který se nazývá P), sada všech prvočísel menších nebo rovných B. Dále kladná celá čísla z jsou hledány tak, že z2 modN je B-hladký. Proto jej lze pro vhodné exponenty zapsat Ai,
Když bylo vygenerováno dost těchto vztahů (obecně postačuje, aby byl počet vztahů o několik více než velikost P), metody lineární algebra lze použít (například Gaussova eliminace ) znásobit tyto různé vztahy takovým způsobem, že exponenty prvočísel na pravé straně jsou všechny sudé:
Tím se získá a shoda čtverců formuláře A2 ≡ b2 (mod N), který může být přeměněn na faktorizaci N, N = gcd (A + b, N) × (N/ gcd (A + b, N)). Tato faktorizace se může ukázat jako triviální (tj. N = N × 1), k čemuž může dojít, pouze pokud A ≡ ±b (mod N), v takovém případě je třeba provést další pokus s jinou kombinací vztahů; ale netriviální dvojice faktorů N lze dosáhnout a algoritmus se ukončí.
Pseudo kód
vstup: kladné celé číslo výstup: netriviální faktor Vyberte vázaný Nechat být všechny prvočísla opakovat pro na dělat Vybrat takhle je -hladký Nechte takhle konec pro Najít neprázdné takhle Nechat zatímco vrátit se
Příklad
Tento příklad se pokusí zohlednit N = 84923 pomocí vázaného B = 7. The faktorová základna je tedy P = {2, 3, 5, 7}. Lze vyhledat celá čísla mezi a N jehož čtverce mod N jsou B-hladký. Předpokládejme, že dvě z nalezených čísel jsou 513 a 537:
Tak
Pak
To znamená
Výsledná faktorizace je 84923 = gcd (20712 - 16800, 84923) × gcd (20712 + 16800, 84923) = 163 × 521.
Optimalizace
The kvadratické síto je optimalizace Dixonovy metody. Vybírá hodnoty X blízko druhé odmocniny z N takhle X2 modulo N je malá, čímž se do značné míry zvyšuje šance na získání hladkého čísla.
Mezi další způsoby, jak optimalizovat Dixonovu metodu, patří použití lepšího algoritmu k řešení maticové rovnice, přičemž se využívá výhod řídkosti matice: číslo z nemůže mít více než faktory, takže každý řádek matice je téměř všechny nuly. V praxi se blokovat Lanczosův algoritmus se často používá. Velikost základny faktorů musí být také zvolena pečlivě: pokud je příliš malá, bude obtížné najít čísla, která by nad ní zcela faktorizovala, a pokud je příliš velká, bude třeba shromáždit více vztahů.
Sofistikovanější analýza využívající aproximaci, že číslo má všechny své hlavní faktory menší než s pravděpodobností asi (přiblížení k Funkce Dickman – de Bruijn ), znamená, že volba příliš malého faktorového základu je mnohem horší než příliš velkého a že ideální velikost základního faktoru je nějaká síla .
Optimální složitost Dixonovy metody je
v big-O notace nebo
v L-notace.
Reference
- ^ Kleinjung, Thorsten; et al. (2010). "Faktorizace 768bitového modulu RSA". Pokroky v kryptologii - CRYPTO 2010. Přednášky z informatiky. 6223. 333–350. doi:10.1007/978-3-642-14623-7_18. ISBN 978-3-642-14622-0.
- ^ Dixon, J. D. (1981). „Asymptoticky rychlá faktorizace celých čísel“. Matematika. Comp. 36 (153): 255–260. doi:10.1090 / S0025-5718-1981-0595059-1. JSTOR 2007743.