Náměty aktivit pro popularizaci matematiky

Příklad 3: Rozložme číslo N = 221 pomocí Pollardovy rho - metody.

Příklad 4: Pomocí Pollardovy rho - metody rozložme číslo N = 989.

Příklad 5: Pomocí Pollardovy rho - metody rozložme číslo N = 4 004 747.

Příklad 6: Pomocí Pollardovy rho - metody rozložme číslo N = 63 797.

Cvičení: Dokažte platnost této věty:

Pro ty, kteří budou chtít naprogramovat kalkulátor podle shora uvedeného návodu, by samozřejmě byla užitečná informace, kolik asi členů posloupnosti  bude nutné vypočítat. Ukazuje se, že pokud N je složené přirozené číslo, p jeho prvočíselný dělitel, pak by měl postačovat výpočet D(x_2t - x_t , N) pro t = 1, 2, ...,  „téměř ve všech případech“ (zde [a] značí celou část čísla a a průběh výpočtu ovšem má nám již známý „pravděpodobnostní“ charakter).

Před třiceti lety byla Pollardova rho - metoda jednou z nejúčinnějších faktorizačních metod. V roce 1981 se např. Brentovi a Pollardovi zdařilo pomocí této metody rozložit osmé Fermatovo číslo  tedy v součin dvou prvočísel majících 16, resp. 62 cifer. Jak je patrné z následující tabulky, dnes již toto postavení ztratila a byla překonána několika efektivnějšími, ovšem i komplikovanějšími metodami. Pro školskou matematiku však má Pollardova rho -  metoda mnohé přednosti - je jednoduchá a přináší mnoho podnětů k samostatné práci žáků, příležitosti k seznámení se s grafickými kalkulátory, resp. se základy programování.

Z knihy [1] je převzata tabulka popisující dobu běhu některých algoritmů užívaných pro faktorizaci přirozeného čísla N délky n na jeho prvočíselné faktory. Doba běhu Lenstrova algoritmu ve skutečnosti nezávisí na n, ale (hlavně) na délce druhého největšího prvočíselného faktoru čísla N. Některé z časových analýz jsou pouze heuristické, ne rigorózně dokázané. Poznamenejme, že velikost vstupu je 

Literatura:

[1] von zur Gathen, J, Gerhard, J.: Modern Computer Algebra, Cambridge University Press, 1999.

[2] Childs, L. N.: A Concrete Introduction to Higher Algebra, Springer, New York, 1979.

[3] Pomerance, C.: Vyprávění o dvou sítech. PMFA, 43 (1998), 9 - 29.

[4] Riesel, H.: Prime Numbers and Computer Methods for Factorization, 2. vydání, Birkhäuser, 1994.

Seznámili jsme se s moderní faktorizační metodou, ale její idea je dostupná i studentu SŠ se zájmem o matematiku.

Informace ke stažení ve formátu pdf zde.