Faktorizacija naravnih števil

Abstract

Keywords

Data

Language:	Slovenian
Year of publishing:	2011
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[P. Bogataj]
UDC:	004(043.2)
COBISS:	8397396
Views:	47
Downloads:	3
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Integer factorization algorithms
Secondary abstract:	The decomposition of a natural number into a product of prime numbers is called factorization. The main problem with factorization is the fact that there is no known efficient algorithm which would factor a given natural number n in polynomial time. The closest equivalent to such an algorithm is Shor's algorithm for quantum computers, which is still not practically applicable. The difficulties with factorization form the basis for modern cryptosystems—the most renowned among them is the RSA algorithm. The purpose of this thesis is to present different algorithms for natural number factorization. For each algorithm, the thesis provides its description, its time complexity and its pseudocode. Some of the algorithms are implemented in the Java Programming Language. The thesis is divided into several parts. The first part describes the mathematical characteristics and the use of factorization. The second part deals with special-purpose algorithms, whose time complexity depends on the properties of the factorized number. The algorithms presented in this part include trial division, Pollard's p-1 and \rho algorithms, Williams' p+1 algorithm, Lenstra elliptic curve factorization, Fermat's factorization method, and Euler's factorization method. The third part deals with general-purpose algorithms, whose time complexity depends solely on the size of the factorized number. These include Dixon's algorithm, the quadratic and number field sieves, the continued fraction factorization, and Shanks' square forms factorization. The conclusion consists of the summaries of the presented algorithms with their time complexities, and provides the guidelines for further research.
Secondary keywords:	factorization;algorithm;time complexity;prime number;greatest common divisor;computer science;diploma;
File type:	application/pdf
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	75 str.
ID:	24009467