| dbpedia-owl:abstract
|
- Test prvočíselnosti je algoritmus z oboru teorie čísel, kterým lze určit, zda je zadané přirozené číslo prvočíslem. Obvykle přitom tuto otázku zodpoví, aniž by přímo našel prvočíselný rozklad (to je považováno za podstatně náročnější úlohu), a často se jedná o pravděpodobnostní algoritmy či algoritmy použitelné jen na určitý druh čísel.Kromě algoritmů, které v případě úspěchu prokáží, že je číslo prvočíslem, jsou také algoritmy, které v případě úspěchu prokáží, že se jedná o složené číslo – takové se někdy označují testy složenosti a jejich zřejmě nejznámějším příkladem je oblíbený Millerův-Rabinův test prvočíselnosti.Testování prvočíselnosti je obecně možné v polynomickém čase, což bylo prokázáno objevením algoritmu AKS v roce 2002. Jedná se ovšem o asymptotickou složitost, při praktickém použití svou rychlostí silně zaostává a jsou často upřednostňovány jiné algoritmy, byť třeba pravděpodobnostní.
|
