20.500.12556/RUL-110523 Polinomsko razpoznavanje praštevil Polynomial primality testing Že tisočletja poznamo problem razpoznavanja praštevil, vendar je to včasih veljalo za bolj teoretičen problem. Šele v 20. stoletju so znanstveniki ugotovili, kako zelo pomemben je ta problem tudi za praktične namene, saj so bili kriptografski sistemi zasnovani na podlagi velikih praštevil. Razvili so se polinomski verjetnosti algoritmi, ki so v praksi zelo uporabni in zadostni za potrebe varnih kriptografskih sistemov, vendar pri izvajanju verjetnostnih algoritmov vedno obstaja majhna možnost, da podajo nepravilen rezultat. Še vedno je obstajalo vprašanje, ali obstaja polinomski deterministični algoritem za razpoznavanje praštevilskosti. Tak algoritem so leta 2002 predstavili trije indijski znanstveniki Agrawal, Kayal in Saxena. V diplomski nalogi smo pregledali najbolj znane algoritme za dan problem in podrobno opisali prvi polinomski deterministični algoritem AKS ter ga dokazali. Predstavljena je tudi implementacija tega algoritma. We have known the problem of prime numbers recognition for thousands of years, but it has been considered a more theoretical problem. It was not until the twentieth century that scientists realized the importance of this problem for practical purposes as well, since cryptographic systems were designed on the basis of large prime numbers. Scientists developed randomized polynomial algorithms, which are in practice very useful and sufficient for the needs of secure cryptographic systems. There was still open question of whether there was a polynomial deterministic algorithm for testing primes. Such an algorithm was introduced in 2002 by three Indian scientists Agrawal, Kayal and Saxena. In the thesis we examined the most known algorithms for the given problem and described the first polynomial deterministic algorithm AKS and proved it. We also presented an implementation of algorithm AKS. AKS algoritem praštevilo AKS algorithm prime number true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2019-09-16 12:25:03 2019-09-16 12:25:06 2022-08-22 03:44:18 0000-00-00 00:00:00 2019 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 23861 1538363331 Kojic_Branka_-_Polinomsko_razpoznavanje_prastevil.pdf Kojic_Branka_-_Polinomsko_razpoznavanje_prastevil.pdf 1 18CE1AB93FE8BB4B0C662494B0D07D7E e9e48b713789ac853c0b5bfdd1387160520cd87a435d9b38fe6e81b5fd08b90d 23f68c1b-a1b7-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=122192 Fakulteta za računalništvo in informatiko 0 0 0