Testovi prostosti i metode faktorizacije brojeva

Iveković, Zvonimir (2016) Testovi prostosti i metode faktorizacije brojeva. Diploma thesis, Faculty of Science > Department of Mathematics.

[img]
Preview
PDF
Language: Croatian

Download (236kB) | Preview
[img] Archive
Language: Croatian

Download (28kB)

Abstract

In this paper six algorithms are presented: three primality tests and three factorization algorithms. Factorization algorithms (methods) are those algorithms that give some decomposition of a given integer n in the sense of Fundamental theorem of arithmetic (1). Primality test are those algorithms that, for a given positive integer n, decide whether n is prime or composite. Although factorization algorithms can also be used for that purpose, it is not common to do so. If they are used for testing, they are only useful for small numbers, because of their complexity. Fastest known factorization methods, as one can see in this paper, are of subexponential time complexity, while primality tests are polynomial. One might find this logical, since it is far easier to decide whether a number is prime, than to give a concrete factorization. Primality tests discussed here are: • Fermat test, which is a corner stone of many primality tests, • Miller–Rabin test, which represents nondeterministic, but fast primality tests, • algorithm AKS, which is so far the only known polynomial algorithm. In practice, AKS usually gives way to algorithms such as Miller–Rabin test, because it is faster, and its nondeterministic component can be arbitrarily reduced to satisfyingly small probability of mistake. Therefore, the importance of AKS is, for now, mostly theoretical. Factorization methods chosen to be represented are: • quadratic sieve method (QS), • number field sieve (NFS), • elliptic curve method (ECM). It is stated here that the time complexity of ECM depends strongly on the size of the least prime factor of the number it is trying to factor. Algorithms with this feature are called first category algorithms. Complexity of QS and NFS depends solely on the size of the number which they are trying to factor. Such algorithms are called Second Category or Kraitchik family algorithms. All three algorithms are of subexponential time complexity, which means that they are faster than exponential algorithms, but slower than any polynomial algorithm (of course, asymptotically). For each algorithm discussed in this paper, the principle on which it is based is explained, as are the basic concepts necessary for understanding it.

Item Type: Thesis (Diploma thesis)
Supervisor: Singer, Saša
Date: 2016
Number of Pages: 29
Subjects: NATURAL SCIENCES > Mathematics
Divisions: Faculty of Science > Department of Mathematics
Depositing User: Iva Prah
Date Deposited: 25 Oct 2016 11:50
Last Modified: 25 Oct 2016 11:50
URI: http://digre.pmf.unizg.hr/id/eprint/5230

Actions (login required)

View Item View Item