Zobrazení zdroje stránky Pollardova p-1 metoda

'''Pollardova p-1 metoda''' je [[algoritmus]] z oboru [[teorie čísel]] sloužící k rozložení [[složené číslo|složených čísel]] na jejich [[prvočíselný rozklad]]. Zveřejnil jej v roce 1974 britský matematik [[John Pollard]] a jedná se o algoritmus vhodný pro složená čísla, jejichž [[Dělitelnost|dělitel]] bez jedné je v nejjednodušší verzi algoritmu [[hladké číslo]], v pokročilých verzích se od hladkosti příliš neodchyluje.

Algoritmus je užitečný pro rozkládání náhodných čísel. V [[kryptografie|kryptografických]] užitích (např. při použití algoritmu [[RSA]]) se s ním počítá a složená čísla se volí tak, aby byla vůči rozložení tímto algoritmem odolná.

== Nejzákladnější podoba ==
Jádrem algoritmu je úvaha vycházející z [[Malá Fermatova věta|Malé Fermatovy věty]], totiž že pro libovolné [[prvočíslo]] <math>p</math> a libovolné s ním [[Nesoudělná čísla|nesoudělné číslo]] <math>a</math> platí
:<math>a^{p-1}\equiv 1\mod{p}</math>, tedy <math>a^{p-1}-1 \equiv 0 \mod{p}</math>, tedy <math>p</math> dělí <math>a^{p-1}-1</math>
Tato rovnost platí i pro případ, kdy <math>p</math> je hledaný prvočíselný dělitel nějakého složeného čísla <math>n</math>. V takovém případě navíc platí, že [[největší společný dělitel]] <math>n</math> a <math>a^{p-1}-1</math> bude dělitelný <math>p</math> (a lze ho rychle spočítat [[Eukleidův algoritmus|Eukleidovým algoritmem]]).  A také platí, že vše výše platí i s [[Umocňování|exponentem]], který není přímo <math>p-1</math>, ale jeho libovolný nenulový násobek. Tedy pokud bude nějaké <math>a</math> umocněno na <math>r= s(p-1)</math>, bude <math>\operatorname{NSD}\left(a^r-1,n\right)</math> dělitelné <math>p</math> a pravděpodobně rovno přímo <math>p</math>. Pro vhodnou volbu <math>r</math> lze tedy tím způsobem získat hodnotu <math>p</math>. Algoritmus dále počítá s tím, že když se vynásobí všechna malá prvočísla až do vhodné meze <math>B</math>, bude (pro náhodné dělitele) s nemalou pravděpodobností <math>p-1</math> skutečně [[hladké číslo|B-hladké]].

== Rozšířená verze ==
Rozšířené verze algoritmu jednak počítají nejen s prvočísly do meze <math>B</math>, ale i s jejich mocninami do dané meze, jednak se pak přidává pronásobení exponentu jednotlivými prvočísly nad mez pro případ, že <math>p-1</math> bylo skoro B-hladké - totiž že by mělo jako dělitele samé mocniny prvočísel menší než B a kromě nich jen jedno prvočíslo jen trochu větší než B. 

Pronásobování jednotlivými exponenty přitom lze provádět poměrně efektivně. Je-li spočítáno <math>b^{p_i}</math> a je potřeba zjistit <math>b^{p_{i+1}}</math>, lze je spočítat vzorcem
:<math>b^{p_{i+1}}=b^{p_i}\cdot b^{p_{i+1}-p_i}</math>
Rozdíl <math>d_i=p_i-p_{i+1}</math> je přitom poměrně malý, takže má krátké vyjádření v [[dvojková soustava|dvojkové soustavě]] <math>d_i=\sum_{j=0}^k2^{t_j}</math> a potom tedy
:<math>b^{p_{i+1}}=b^{p_i}\cdot\prod_{j=0}^kb^{2^{t_j}}</math>
Hodnoty <math>b</math> umocněné na mocniny dvou lze přitom mít předpočítané v tabulce a místo mocnění lze tedy změnu velkého prvočísla v exponentu realizovat rychlejším násobením.

== Složitost ==
Algoritmus má v nejhorším případě [[exponenciální časová složitost|exponenciální časovou složitost]], ovšem vhodný typ dělitelů dokáže najít velmi rychle.

[[Kategorie:Faktorizační algoritmy]]