Diskretni logaritem

diplomsko delo

Barbara Petelinek (Avtor), Dušan Pagon (Mentor)

Povzetek

V diplomskem delu obravnavamo problem diskretnega logaritma. Problem diskretnega logaritma je matematično-računski problem, ki služi kot osnova kriptografskim protokolom. Pri diskretnih logaritmih operiramo znotraj multiplikativne grupe G. Problem od nas zahteva, da za dani g,h je element G najdemo x je element G, za katerega je g^x=h. Povedano drugače iščemo logaritem x=log_g h, ker pa logaritem operira v končni multiplikativni grupi, mu pravimo diskretni. Ta problem diskretnega logaritma je domnevno težko rešljiv, ker zanj ne poznamo splošne rešitve. Dolgotrajno in neuspešno iskanje učinkovitih algoritmov pa nas utrjuje v domnevi,da je diskretni logaritem v splošnem težko izračunati v naslednjih multiplikativnih grupah: - Z^*_p, kjer je p praštevilo; - multiplikativna grupa reda p^k, kjer je p praštevilo; - grupa točk eliptične krivulje, definirane nad končnim poljem. V diplomskem delu je poudarek na metodah za izračun vrednosti diskretne logaritemske funkcije (številskih rešetih. Le-te pa so v marsičem podobne tistim za razcep naravnega števila na prafaktorje.

Ključne besede

matematika;diskretni logaritem;grupe;algoritmi;kriptografija;številsko polje;rešeto;diplomska dela;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2010
Izvor:	Maribor
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[B. Petelinek]
UDK:	51(043.2)
COBISS:	17739784
Št. ogledov:	2481
Št. prenosov:	195
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Discrete logarithm
Sekundarni povzetek:	In this diploma work we have presented the discrete logarithm problem. Discrete logarithm is mathematic-computational problem, which serves as basis for cryptographic protocols. Discrete logarithms are operated only inside multiplicated group G. The main problem is finding a solution x, of the equation g^x=h, where g and h are elements of a finite cyclic group G. In other words we are searching for logarithm x=log_g h and because logarithm operates on finite multiplicated group, x is called a discrete logarithm to the base g of h in the group G. The problem of discrete logarithm is not very easy to solve, because there is no general solution for the problem. Lasting and unsuccessful search of efficient algorithms show us that computation of discrete logarithm is in general very hard to solve in next multiplicative groups: - Z^*_p, where p is prime number; - multiplicated group of order p^k, where p is prime number; - group of points on ecliptic curve, defined over finite field. The emphasis in this diploma work is on methods that compute values for discrete logaritm function (number field sieve). These sieves are very familiar to those that are used for splitting of natural number to prime numbers.
Sekundarne ključne besede:	Discrete logarithm;group;algorithm;cryptography;number field sieve.;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	29 f.
Ključne besede (UDK):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	18597