Polinomski algoritmi za testiranje praštevilskosti

Published on 2007-02-253867 Views

Miha Vuk

Ugotoviti, ali je neko število praštevilo, ni težko, zares učinkovitega postopka za to pa se vedno ne poznamo. Gre za enega klasičnih problemov, za katerega znanstveniki se vedno odkrivajo nove, bo

Solomon seminar

Presentation

Polinomski algortimi za testiranje00:00

Predstavili bomo:00:55

Praštevila03:26

Vrste algoritmov04:29

Gostota praštevil08:15

Lastnosti praštevil10:14

PRIMES je v razredu NP in n-1 testi12:22

Mersennova (pra)števila16:35

Verjetnostni in deterministični algoritmi17:38

Najboljši algoritmi pred letom 200223:57

Dokazljiva praštevila29:41

Algoritem Agrawal-Kayal-Saxsena32:16

Izboljšave AKS in sorodni algoritmi42:24

Testiranje srednjih praštevil (10-100 bitov)45:47

Testiranje velikih praštevil53:20

Združeni rezultati testiranja praštevil55:19

Generiranje velikih praštevil56:31

Komentar rezultatov57:48