Polinomsko razpoznavanje praštevil

diplomsko delo

Branka Kojić (Author), Borut Robič (Mentor)

Abstract

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

Keywords

AKS;algoritem;praštevilo;računalništvo;računalništvo in informatika;računalništvo in matematika;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Data

Language:	Slovenian
Year of publishing:	2019
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[B. Kojić]
UDC:	004(043.2)
COBISS:	1538363331
Views:	679
Downloads:	141
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Polynomial primality testing
Secondary 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.
Secondary keywords:	AKS;algorithm;prime number;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000407
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	40 str.
ID:	11225337