Polinomsko razpoznavanje praštevil

diplomsko delo

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

Povzetek

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

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2019
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[B. Kojić]
UDK:	004(043.2)
COBISS:	1538363331
Št. ogledov:	679
Št. prenosov:	141
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Polynomial primality testing
Sekundarni povzetek:	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.
Sekundarne ključne besede:	AKS;algorithm;prime number;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000407
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	40 str.
ID:	11225337