Diskretni logaritem

diplomsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2010
Source:	Maribor
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[B. Petelinek]
UDC:	51(043.2)
COBISS:	17739784
Views:	2481
Downloads:	195
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Discrete logarithm
Secondary abstract:	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.
Secondary keywords:	Discrete logarithm;group;algorithm;cryptography;number field sieve.;
URN:	URN:SI:UM:
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	29 f.
Keywords (UDC):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	18597