A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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 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á verze
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ž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.
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk