Pollardova p-1 metoda

Technology

12 hours ago

Author

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ř. +more 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). +more 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}^k2^{t_j} a potom tedy :b^{p_{i+1}}=b^{p_i}\cdot\prod_{j=0}^kb^{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.