Binarni polinomi

master's thesis

• Author: Jure Šiljeg
• Mentor: Goranka Nogo (mentor)
• Committee member: Goranka Nogo (predsjednik povjerenstva)
• Committee member: Zvonimir Tutek (član povjerenstva)
• Committee member: Dijana Ilišević (član povjerenstva)
• Committee member: Marko Tadić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2017-02-24, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu smo definirali binarne polinome i opisali operacije nad njima. Objasnili smo ključne točke algoritama, dali primjere izvrijednjavanja i analizirali složenosti uz popratne komentare. Za množenje i potenciranje smo ponudili nekoliko verzija algoritama dok su dijeljenje i zbrajanje zbog, respektivno, okvira rada i jednostavnosti, obrađeni na prigodi suvisao način. Faktorizaciju smo, pak, detaljno razradili i u konačnici objasnili kako doći do generaliziranog pristupa u rastavu bilo kojeg polinoma. Zaključili smo da je hibridni Karatsubin brži od Karatsubinog, a Karatsubin od naivnog množenja. Testna vremena se slažu s teorijskim predviđanjima za algoritme množenja. Također je jasno postalo da se polinomi mogu posebno efikasno zbrajati i oduzimati zbog jednostavnosti algoritma, a dali smo rezultate i za ostale operacije. Vidljivo je da za složenije ulaze ne možemo tako brzo dobiti rezultate: dijeljenje u slučaju djelitelja sa stupnjem preko milijun; faktorizacija svih polinoma stupnja većeg od dvadeset.

Abstract (english)

In this thesis we presented binary polynomials through definition and operations on them. We explained key points of algorithms, gave examples of evaluation, pseudocodes of algorithms itself and analysed time complexity with comments in form suitable for appropriate thesis. We also offered few versions of algorithm for multiplication and exponentiation, and gave appropriate care and explanation with pseudocodes for division and addition. Factorization was described in detail: all necessary key steps for general approach in getting factors. We concluded that hybrid Karatsuba has better time complexity than Karatsuba, and Karatsuba is, in Big-O notation, faster than simple multiplication algorithm. Testing times are in accordance with theoretical predictions for multiplication algorithms. Also, addition and subtraction may be extremely fast because of simplicity of algorithm itself and structure of GF(2). We provided results for the rest of operations, too. It is obvious that we are not able to get results very fast when input size grows: division in case of divident’s degree higher than one million and factorization of polynomials with degree higher than twenty.

• Keywords: binarni polinom; Karatsubin; operacije nad binarnim polinomima
• Keywords (english): binary polynomials; Karatsuba; operations on binary polynomials
• Language: croatian
• URN:NBN: urn:nbn:hr:217:712904
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2017-04-28 10:53:30