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 ${\displaystyle p}$ a libovolné s ním nesoudělné číslo ${\displaystyle a}$ platí

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

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

Rozšířená verze

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

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

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

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

Hodnoty ${\displaystyle 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.