Polinomsko razpoznavanje praštevil

KOJIĆ, BRANKA (author), Robič, Borut (mentor)

Ž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.

• Language: Slovenian
• Keywords: AKS, algoritem, praštevilo
• Work type: Bachelor thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2019
• PID: 20.500.12556/RUL-110523
• COBISS.SI-ID: 1538363331
• Publication date in RUL: 16.09.2019

KOJIĆ, BRANKA, 2019, Polinomsko razpoznavanje praštevil [online]. Bachelor’s thesis. [Accessed 31 March 2025]. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=110523

Secondary language

• Language: English
• Title: Polynomial primality testing

Abstract

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.

• Keywords: AKS, algorithm, prime number