Prvočíslo

Existuje jednoduchá metoda, jak najít seznam prvočísel. Vytvořil ji Eratosthenes. Má název Eratosthenovo síto. Zachycuje čísla, která nejsou prvočísla (jako síto), a prvočísla nechává projít.

Metoda pracuje se seznamem čísel a speciálním číslem b, které se v průběhu metody mění. Při postupu metodou některá čísla v seznamu zakroužkujete a jiná vyškrtnete. Každé zakroužkované číslo je prvočíslo a každé přeškrtnuté číslo je složené. Na začátku jsou všechna čísla prostá: nejsou zakroužkována ani přeškrtnuta.

Metoda je vždy stejná:

1. Na list papíru napište všechna celá čísla od 2 až po testované číslo. Číslo 1 nezapisujte. Přejděte k dalšímu kroku.
2. Začněte s hodnotou b rovnou 2. Přejděte k dalšímu kroku.
3. V seznamu zakroužkujte písmeno b. Přejděte na další krok.
4. Počínaje číslem b spočítejte v seznamu další b a toto číslo vyškrtněte. Opakujte počítání dalších b čísel a škrtání čísel až do konce seznamu. Přejděte k dalšímu kroku.
• (Například: Když je b 2, zakroužkujete 2 a přeškrtnete 4, 6, 8 atd. Když je b 3, zakroužkujete 3 a přeškrtnete 6, 9, 12 atd. Hodnoty 6 a 12 již byly přeškrtnuty. Přeškrtněte je znovu.)
5. Zvětšete b o 1. Přejděte k dalšímu kroku.
6. Pokud bylo b přeškrtnuto, vraťte se k předchozímu kroku. Pokud je b číslo v seznamu, které nebylo přeškrtnuto, přejděte ke 3. kroku. Pokud b není v seznamu, přejděte k poslednímu kroku.
7. (Toto je poslední krok.) Hotovo. Všechna prvočísla jsou zakroužkována a všechna složená čísla jsou přeškrtnuta.

Tuto metodu můžete například použít na seznamu čísel od 2 do 10. Na konci budou zakroužkována čísla 2, 3, 5 a 7. Jsou to prvočísla. Čísla 4, 6, 8, 9 a 10 budou přeškrtnuta. Jsou to složená čísla.

Tato metoda nebo algoritmus trvá příliš dlouho, než se najdou velmi velká prvočísla. Je však méně komplikovaný než metody používané pro velmi velká prvočísla, jako je Fermatův test prvočíselnosti (test, který zjišťuje, zda je číslo prvočíslo či nikoli) nebo Millerův-Rabinův test prvočíselnosti.

Prvočísla jsou velmi důležitá v matematice a informatice. Níže jsou uvedena některá reálná použití. Velmi dlouhá čísla se obtížně řeší. Je obtížné najít jejich prvočinitele, proto se většinou čísla, která jsou pravděpodobně prvočísla, používají k šifrování a tajným kódům.

• Většina lidí má bankovní kartu, kterou si může vybrat peníze ze svého účtu pomocí bankomatu. Tato karta je chráněna tajným přístupovým kódem. Protože kód musí být utajen, nemůže být na kartě uložen v otevřeném textu. K tajnému uložení kódu se používá šifrování. Toto šifrování využívá násobení, dělení a hledání zbytků velkých prvočísel. V praxi se často používá algoritmus zvaný RSA. Využívá čínskou větu o zbytcích.

• Pokud má někdo u svého e-mailu digitální podpis, používá se šifrování. Tím je zajištěno, že nikdo nemůže e-mail od něj zfalšovat. Před podpisem se vytvoří hashová hodnota zprávy. Ta se pak zkombinuje s digitálním podpisem a vznikne podepsaná zpráva. Používané metody jsou víceméně stejné jako v prvním výše uvedeném případě.

• Hledání největšího dosud známého prvočísla se stalo svého druhu sportem. Testování, zda je číslo prvočíslo, může být obtížné, pokud je číslo velké. Největšími známými prvočísly jsou obvykle Mersennova prvočísla, protože nejrychlejším známým testem prvočíselnosti je Lucasův-Lehmerův test, který se opírá o speciální tvar Mersennových čísel. Skupina, která hledá Mersennova prvočísla, je zde[1].