Sito polja brojeva

Maltarski, Dario (2014) Sito polja brojeva. Diploma thesis, Faculty of Science > Department of Mathematics.

[img]
Preview
PDF
Language: Croatian

Download (403kB) | Preview

Abstract

Before computer development algorithm complexity was not important and didn’t exist as a branch of mathematics since algorithms had to be carried out ”on paper”. Factorization had no practical importance, and it was usually practiced by mathematicians out of curiosity, and the better ones tried to implement new ideas and find new algorithms for factorization, which resulted in algorithms such as Fermat factorization or Euler’s algorithm. With the development of computers and algorithm complexity theory, as well as the importance of factorization in cryptography, complexity of factorization algorithms has become a very important factor which resulted in the emergence of a number of new fast algorithms. Many of these algorithms are based on older algorithms. We have shown how the rational, quadratic and special sieve are based on Fermat factorization. Despite the introduction of new ideas into the aforementioned algorithms, which made a step further in regards to Fermat factorization in terms of time complexity, an algorithm which would factorize large numbers in polynomial time has still not been found. At one point, some mathematicians thought that the time complexity of each algorithm for factorization is $\Omega (e^{\sqrt{\log{(n)}\log{(\log{(n))}}}})$ since all the best algorithms had this complexity, and none had better, but then appeared the general number field sieve algorithm. Today, in the same way we wonder if the complexity of factorization problem is at best equal to the complexity of the general sieve, ie. $\Omega(e^{c {(\log{(n)})}^{1/3}{(\log{(\log{(n)})})}^{2/3} })$. The appearance of the quadratic in 1981. as well as the special and the general sieve in 1988-1990 meant a great step forward in improving the speed of factorization of large numbers, but after that, all progress in factorization of numbers can be attributed solely to the development of computers and distributed computing. Developing faster factorization algorithms than the general sieve doesn’t seem likely at the moment, and creating a polynomial algorithm seems almost impossible. Let’s suppose for a moment that faster algorithm than the general sieve exists. Such an algorithm in my opinion would not have been the result of optimization of sieve algorithms, but would likely be a result of working with other algorithms and finding new approaches and ideas in the factorization of numbers. Besides finding a faster algorithm for today’s computers, the problem of factorization of large numbers could be solved in polynomial time with quantum computation if such computation would be possible.

Item Type: Thesis (Diploma thesis)
Supervisor: Najman, Filip
Date: 2014
Number of Pages: 44
Subjects: NATURAL SCIENCES > Mathematics
Divisions: Faculty of Science > Department of Mathematics
Depositing User: Iva Prah
Date Deposited: 03 Jun 2015 12:44
Last Modified: 03 Jun 2015 12:44
URI: http://digre.pmf.unizg.hr/id/eprint/4001

Actions (login required)

View Item View Item