Prvočísla Flashcards
Typy prvočísel
Mersennova 𝑀𝑝 = 2𝑛 − 1 (např. 31)
Mersennova prvočísla jsou úzce spojena s dokonalými čísly, což jsou čísla, která se rovnají součtu svých dělitelů (např. 6 a 28).
Hledání Mersennových prvočísel je populární v matematice a používá se k testování výpočetní síly superpočítačů (projekt GIMPS).
Sophie-Germain 𝑝 pokud 2𝑝 + 1 je také prvočíslo (např. 11).
Používají se v kryptografii, zejména v systému ElGamal a Diffie-Hellman, protože 2p+1 je bezpečné prvočíslo (viz dále).
Bezpečnná 𝐵𝑝 = 2𝑝 + 1 (např. 23).
Bezpečná prvočísla jsou důležitá v kryptografii, protože jejich struktura zajišťuje, že výpočetní problémy spojené s nimi jsou složité.
Používají se při generování kryptografických klíčů, protože jsou odolná vůči určitým typům útoků (např. útokům na diskretizaci v eliptických křivkách).
Generování - Eratostenovo síto
Eratostenovo síto - Pro malá prvočísla se často používají deterministické metody, které systematicky vylučují složená čísla a je velmi efektivní pro generování menších prvočísel.
Představte si síto jako filtr, který odděluje složená čísla (násobky menších čísel) od prvočísel.
Generování - Fermatův test
Fermatův Test - Fermatův test je založen na Fermatově malé větě, která říká, že pokud je 𝑝 p prvočíslo a 𝑎 je číslo nesoudělné s
𝑝 p, platí: a^(p−1) ≡1 (mod p)
Proč je test pouze “pravděpodobnostní”?
Existují Carmichaelova čísla (např. 561), která nejsou prvočísla, ale splňují Fermatovu malou větu pro všechna 𝑎 a, která jsou nesoudělná s 𝑛 n. Tato čísla způsobují, že Fermatův test není spolehlivý sám o sobě.
Generování - Miller Rabin
Miller-Rabinův test - Funguje na principu vlastností modulo aritmetiky: Pokud 𝑛 n projde testem pro několik náhodně zvolených čísel, existuje velmi vysoká pravděpodobnost, že je 𝑛 prvočíslo. Millerův–Rabinův test je jako prověrka, kde číslo 𝑛 musí splnit několik kritérií, aby bylo považováno za prvočíslo. Pokud projde test několikrát, je to jako když student na zkoušce několikrát správně odpoví na otázky – můžeme mu důvěřovat.
Na rozdíl od Fermatova testu Miller-Rabinův test eliminuje Carmichaelova čísla díky tomu, že zohledňuje více podmínek
Generování - Skutečný test
Skutečný test- Pro hledání Mersennových prvočísel (
𝑀𝑝=2^p −1) se používají speciální algoritmy, např. Lucas-Lehmerův test, který testuje, zda 𝑀𝑝 je prvočíslo.
V budoucnu by šlo využít kvantové počítače.
