Kryptografie
Přihlásit se

Test prvočíselnosti

Proč jsou některé příklady s prvočísly tak složité? Prozkoumejme to pomocí testů prvočíselnosti.

Tento obsah spravuje Daniel Hollas.

50 minut

Co je to počítač? 5 m

Dříve, než se začneme zabývat efektivitou algoritmu, musíme pochopit, jak definovat rychlost algoritmu (časovou náročnost) podle počtu primitivních kroků.

Co je to počítačová pamět? 5 m

Co je to počítačová pamět? Ukážeme si děrné štítky, feritovou pamět a pamět na bázi atomu. Je velmi důležité si uvědomit, že pamět fyzicky zabírá místo.

Efektivita algoritmů 9 m

Jak můžeme vylepšit rychlost testu prvočíselnosti?

Eratosthenovo síto 4 m

Eratosthenovo síto umožňuje generovat posloupnost prvočísel vyškrtáváním složených čísel z pole čísel. Jak to funguje?

Prvočíselná věta: hustota prvočísel 7 m

Jak můžeme odhadnout počet prvočísel na zadaném intervalu?

Kompromis mezi pamětí a časem 7 m

Jaké jsou hranice paměti? Jak můžeme šetřit časem na úkor prostoru?

RSA šifrování: souhrn - a jak dál? 7 m

Proč je rozklad na prvočísla složitý, zatímco jejich generování je snadné? Kam dále směřujeme?