Naslov Sito polja brojeva Autor Dario Maltarski Mentor Filip Najman (mentor)Član povjerenstva Filip Najman (predsjednik povjerenstva)Član povjerenstva Andrej Dujella (član povjerenstva)Član povjerenstva Goran Muić (član povjerenstva)Član povjerenstva Ivica Nakić (član povjerenstva)Ustanova koja je dodijelila Sveučilište u Zagrebu Datum i država obrane 2014-09-26, Hrvatska Znanstveno / umjetničko PRIRODNE ZNANOSTI Sažetak Prije razvoja računala složenost algoritama nije bila važna te ni nije postojala kao grana matematike budući da su algoritmi morali biti provedeni ručno, "na papiru". Faktorizacija nije imala nikakvu praktičnu važnost te su se njome obično bavili matematičari iz radoznalosti, a oni malo bolji su pokušavali implementirati nove ideje i pronaći nove algoritme za faktorizaciju, te su tako i nastali algoritmi poput Fermatove faktorizacije ili Eulerovog algoritma. Razvojem računala i teorije složenosti algoritama te zbog važnosti faktorizacije u kriptografiji, složenost algoritama za faktorizaciju velikih brojeva je postala vrlo bitan faktor što je rezultiralo pojavom niza novih brzih algoritama. Mnogi od tih algoritama imaju temelje u starijim algoritmima. Mi smo pokazali kako se algoritmi racionalnog, kvadratnog i specijalnog sita baziraju na Fermatovoj faktorizaciji. Usprkos tome što su dodavanjem novih ideja navedeni algoritmi otišli korak dalje od Fermatove faktorizacije u smislu vremenske složenosti, još uvijek nije pronađen algoritam koji bi u polinomnom vremenu netrivijalno faktorizirao velike brojeve. U jednom trenutku su neki matematičari smatrali da je vremenska složenost svakog algoritma za faktorizaciju \(\Omega (e^{\sqrt{\log{(n)}\log{(\log{(n))}}}})\) budući da su svi najbolji algoritmi imali tu složenost, a nijedan bolju, no tada se pojavio algoritam općeg sita brojeva. Danas se na isti način pitamo je li složenost svakog algoritma za faktorizaciju u najboljem slučaju jednaka složenosti općeg sita, tj. q(\Omega(e^{c {(\log{(n)})}^{1/3}{(\log{(\log{(n)})})}^{2/3} })\). Pojave kvadratnog 1981. god. te specijalnog i općeg sita polja brojeva 1988-1990. god. značile su veliki iskorak u brzini faktorizacije velikih brojeva, no nakon toga svaki napredak u faktorizaciji brojeva možemo zahvaliti isključivo razvoju računala i distribuiranog računanja. Osmisliti brži algoritam za faktorizaciju od općeg sita trenutno nije izgledno, a osmisliti polinoman algoritam izgleda gotovo nemoguće. Pretpostavimo na trenutak da je ipak moguće smisliti brži algoritam od općeg sita. Takav algoritam po mom mišljenju ne bi bio rezultat optimizacije algoritama sita brojeva, već bi prije bio rezultat rada s drugim algoritmima i pronalaska novih pristupa i ideja u faktorizaciji brojeva. Osim pronalaženja bržih algoritama za današnja računala problem faktorizacije velikih brojeva moglo bi se rješiti u polinomnom vremenu kvantnim računanjem ukoliko je ono moguće.
Sažetak (engleski) 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.
Ključne riječi
algoritmi za faktorizaciju velikih brojeva
Fermatova faktorizacija
sita
Ključne riječi (engleski)
algorithms for factorization of large numbers
Fermat factorization
sieve
Jezik hrvatski URN:NBN urn:nbn:hr:217:017849 Studijski program Naziv: Računarstvo i matematika Vrsta resursa Tekst Način izrade datoteke Izvorno digitalna Prava pristupa Otvoreni pristup Uvjeti korištenja Datum i vrijeme pohrane 2019-01-21 12:05:17
