Pseudoprvočíslo

Technology

12 hours ago

Author

Jako pseudoprvočísla se v teorii čísel označují taková celá čísla, která jsou sice složená, ale přitom splňují některé z testů, které dokáží většinu složených čísel odlišit od prvočísel. (Takové testy platí pro všechna prvočísla, ale většina složených čísel jim nevyhoví.) Jednotlivé druhy pseudoprvočísel jsou definovány podle konkrétních testů, kterými je nelze rozlišit od prvočísla.

Základní skupinou pseudoprvočísel jsou ta definovaná na základě Malé Fermatovy věty; pokud se hovoří o „pseudoprvočíslech“ bez upřesnění, míní se jimi zpravidla právě tato.

Druhy pseudoprvočísel

Fermatova pseudoprvočísla, Carmichaelova čísla

Malá Fermatova věta popisuje rovnost platnou pro všechna prvočísla, splňují ji však i některá čísla složená, která jsou proto označována jako pseudoprvočísla. Fermatovým pseudoprvočíslem se tedy nazývá takové složené číslo n, které splňuje (pro některé s ním nesoudělné celé číslo a) vztah: :a^{n-1} \equiv 1 \pmod n

Příkladem pseudoprvočísla při základu 5 je číslo 4, neboť :5^{4-1} = 125, přičemž 125 \equiv 1 \pmod 4.

Existují dokonce čísla, u kterých tato rovnost platí pro libovolný základ a. Taková čísla se nazývají Carmichaelova čísla. +more Několik prvních Carmichaelových čísel je 561, 1105, 1729, 2465, 2821, … (sekvence A002997 v OEIS). Je dokázáno, že Carmichaelových čísel existuje nekonečně mnoho.

Číslo, které je Fermatovým pseudoprvočíslem při základu 2, se označuje jako Pouletovo číslo. Prvních několik Pouletových čísel je 341, 561, 645, 1105, 1387, … (sekvence A001567 v OEIS).

Silná pseudoprvočísla

Složené číslo n = d \cdot 2^s + 1 se označuje jako silné pseudoprvočíslo v (s ním nesoudělném) základu a, pokud platí alespoň jedna z následujících dvou podmínek: * a^d \equiv 1 \pmod n, * a^{d \cdot 2^r} \equiv -1 \pmod n \qquad \mathrm{pro~n{\check e}kter{\acute e}~} 0 \le r \le s-1.

Eulerova-Jacobiho pseudoprvočísla

Jako Eulerovo-Jacobiho pseudoprvočíslo o základu a se označuje liché složené číslo n (nesoudělné s a), pro jehož Jacobiho symbol (\tfrac{a}{n}) platí: : (\tfrac{a}{n}) \equiv a^{\frac{n-1}{2}} \pmod n

Další pseudoprvočísla

Další pseudoprvočísla lze definovat na základě libovolného nedokonalého testu prvočíselnosti. Existují proto mimo jiné: * Eliptické pseudoprvočíslo * Eulerovo pseudoprvočíslo * Fibonacciho pseudoprvočíslo * Frobeniovo pseudoprvočíslo * Lucasovo pseudoprvočíslo * Perrinovo pseudoprvočíslo * Somerovo-Lucasovo pseudoprvočíslo

Aplikace, testování prvočíselnosti

Pseudoprvočísla jsou důležitá pro testování prvočíselnosti, neboť způsobují, že některé potenciální testy nejsou spolehlivé.

Mnoho aplikací (např. v kryptografii pro generování klíčů v algoritmu RSA) potřebuje rychle generovat velmi velká prvočísla. +more Možným přístupem je náhodně generovat velká lichá čísla a testovat, zda jsou prvočísla; k tomu je potřeba rychlý test prvočíselnosti. Jednoduchým kandidátem na takový test je vztah podle Malé Fermatovy věty, avšak její splnění ještě nezaručuje, že je číslo prvočíslem, může se jednat pouze o pseudoprvočíslo. Pro některé aplikace to nemusí vadit a mohou používat přímo pseudoprvočísla.

V jiných případech je potřeba použít silnější kritérium. U některých typů pseudoprvočísel neexistuje obdoba Carmichaelových čísel, tedy u nich vždy záleží na základu, vůči kterému se testuje, a každé složené číslo je možné takovým testem odhalit, pokud se použije vhodný základ. +more To vede k možnosti pravděpodobnostních algoritmů pro testování prvočíselnosti: test se provede vůči mnoha náhodně zvoleným základům, jakmile pro jediný základ nevyhoví, je zřejmé, že se jedná o číslo složené. Pokud je však test pro všechny báze splněn, jedná se s jistou pravděpodobností (tím vyšší, čím více testů bylo provedeno) o prvočíslo.