Prvočíselnost (obsah)

Oblíbeným algoritmem začátečníků je elementární test prvočíselnosti, ve kterém se u testovaného čísla zkouší všichni jeho možní dělitelé a pokud žádný z nich nedělí toto číslo, pak jsme našli prvočíslo. Zarážkou, do které se testuje, je odmocnina z testovaného čísla, protože nejhorší možná situace, která může nastat, je, když má číslo jen dva dělitele a ti jsou totožní (odmocnina). Pokud by nebyli totožní, tak je jeden určitě menší a druhy větší ...

Eratosthenovo síto je jednoduchý algoritmus pro nalezení všech prvočísel nižších, než je daná horní mez. Tento algorimus je připisován starořeckému učenci Eratosthenovi z Kyrény a je datován cca. do roku 200 př.n.l. Jedná se o jednu z nejefektivnějších metod pro hledání pročísel do . Pro prvočísla vyšší hodnoty je vhodné využít jiných testů (Rabin-Millerův test, Lehmannův test...). Princip Algoritmus se skládá z následujících kroků: Napíšem...

Fermatův test prvočíselnosti vychází z malé Fermatovy věty, tedy že pro každé prvočíslo platí Pokud rovnost pro testovené číslo p neplatí, tak určitě není prvočíslem, pokud platí, tak dané číslo MOŽNÁ prvočíslem je. Příklad Testujeme: 15 Volíme: a = 2 Musí tedy platit Předpokládáme: Testujeme: 2 je svědkem, že 15 není prvočíslo. Zkusme si ten samý příklad se zvoleným číslem 4 Volíme: a = 4 Musí tedy platit Předpokládáme: Testujeme...

Z malé Fermatovy věty víme, že platí Proto také určitě platí Použijeme-li vzorec , tak dostáváme Z dělitelnosti čísel víme, že musí platit Aby tedy platila rovnice , tak musí platit jedna z následujích podmínek Pokud tedy Pak je číslo p možná prvočíslo. V každém jiném případě prvočíslem určitě není (odporuje malé Fermatově větě). Dá se ukázat, že při každém průchodu tohoto algoritmu dojde k vyloučení padesáti proce...

Rabin-Millerův test (Miller-Rabinův test) je test prvočíselnosti - určuje, zda-li je číslo prvočíslem nebo ne. Ačkoliv byl tento test ve své původní verzi vymyšlené Gary Lee Millerem deterministický, tak závisel na nedokázané Riemannově domněnce. Test byl později upraven Michaelem O. Rabinem do své pravděpodobnostní verze. Rabin-Millerův test stanoví, zda je číslo prvočíslem s pravděpodobností , kde k je počet iterací testu. Princip Z malé Ferm...