Pollardova p-1 metoda

Pollardova p-1 metoda je algoritmus z oboru teorie čísel sloužící k rozložení 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ě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 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é Fermatovy věty, totiž že pro libovolné prvočíslo $p$ a libovolné s ním nesoudělné číslo $a$ platí

$a^{p-1}\equiv 1\mod {p}$, tedy $a^{p-1}-1\equiv 0\mod {p}$, tedy $p$ dělí $a^{p-1}-1$

Tato rovnost platí i pro případ, kdy $p$ je hledaný prvočíselný dělitel nějakého složeného čísla $n$. V takovém případě navíc platí, že největší společný dělitel $n$ a $a^{p-1}-1$ bude dělitelný $p$ (a lze ho rychle spočítat Eukleidovým algoritmem). A také platí, že vše výše platí i s exponentem, který není přímo $p-1$, ale jeho libovolný nenulový násobek. Tedy pokud bude nějaké $a$ umocněno na $r=s(p-1)$, bude $\operatorname {NSD} \left(a^{r}-1,n\right)$ dělitelné $p$ a pravděpodobně rovno přímo $p$. Pro vhodnou volbu $r$ lze tedy tím způsobem získat hodnotu $p$. Algoritmus dále počítá s tím, že když se vynásobí všechna malá prvočísla až do vhodné meze $B$, bude (pro náhodné dělitele) s nemalou pravděpodobností $p-1$ skutečně B-hladké.

Rozšířená verze

Rozšířené verze algoritmu jednak počítají nejen s prvočísly do meze $B$, 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 $p-1$ 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 $b^{p_{i}}$ a je potřeba zjistit $b^{p_{i+1}}$, lze je spočítat vzorcem

$b^{p_{i+1}}=b^{p_{i}}\cdot b^{p_{i+1}-p_{i}}$

Rozdíl $d_{i}=p_{i}-p_{i+1}$ je přitom poměrně malý, takže má krátké vyjádření v dvojkové soustavě $d_{i}=\sum _{j=0}^{k}2^{t_{j}}$ a potom tedy

$b^{p_{i+1}}=b^{p_{i}}\cdot \prod _{j=0}^{k}b^{2^{t_{j}}}$

Hodnoty $b$ 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í časovou složitost, ovšem vhodný typ dělitelů dokáže najít velmi rychle.