Pollardova p-1 metoda

(přesměrováno z Pollardův p-1 algoritmus)

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ší podobaEditovat

Jádrem algoritmu je úvaha vycházející z Malé Fermatovy věty, totiž že pro libovolné prvočíslo   a libovolné s ním nesoudělné číslo   platí

 , tedy  , tedy   dělí  

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

Rozšířená verzeEditovat

Rozšířené verze algoritmu jednak počítají nejen s prvočísly do meze  , 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   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   a je potřeba zjistit  , lze je spočítat vzorcem

 

Rozdíl   je přitom poměrně malý, takže má krátké vyjádření v dvojkové soustavě   a potom tedy

 

Hodnoty   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žitostEditovat

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