Aritmetika konačnih polja

diplomski rad

• Naslov (engleski): Arithmetic of finite fields
• Autor: Martin Matijević
• Mentor: Andrej Dujella (mentor)
• Član povjerenstva: Andrej Dujella (predsjednik povjerenstva)
• Član povjerenstva: Marko Tadić (član povjerenstva)
• Član povjerenstva: Goranka Nogo (član povjerenstva)
• Član povjerenstva: Ljiljana Arambašić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2022-09-27, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu smo obradili pitanja reprezentacije elemenata u konačnim poljima te efiksne implementacije operacija na konačnim poljima. Na početku smo se prisjetili osnovnih algebarskih struktura - grupa, prstena i polja. Uveli smo pojam konačnog, prostog i proširenog polja. Konačna polja smo reprezentirali ireducibilnim polinomima. Pokazali smo kako u programskom paketu PARI/GP odraditi aritmetičke operacije na polinomima iz F2[x]. Objasnili smo kako odabrati definirajući polinom nekog proširenog polja Fpn . Pokazali smo kako implementirati zbrajanje, oduzimanje i množenje u proširenim poljima karakteristike 2 i 3. Za algoritam množenja smo pojasnili ubrzanje algoritma u vidu češalj metoda. Dali smo algoritam za modularnu redukciju. Dali smo algoritme za računanje inverza - Euklidov i binarni te ubrzanje binarnog.

Sažetak (engleski)

In this paper, we dealt with the issues of representation of elements in finite fields and efficient implementation of operations on finite fields. At the beginning, we remind ourselves of the basic algebraic structures - groups, rings and fields. We have introduced the concept of finite, prime and extended field. We represented the finite fields with irreducible polynomials. We have shown how to perform arithmetic operations on polynomials from F2[x] in the program package PARI/GP. We explained how to choose defining polynomial of some extended field Fpn . We have shown how to implement addition, subtraction and multiplication in the extended fields of characteristics 2 and 3. For the multiplication algorithm, we have clarified the acceleration of the algorithm in the form of comb methods. We have provided an algorithm for modular reduction. We have provided algorithms for calculating the inverse - Euclidean and binary and acceleration of the binary.

• Ključne riječi: grupa; prsten; polje; ireducibilni polinomi; programski paket PARI/GP; ubrzanje algoritma; češalj metoda
• Ključne riječi (engleski): groups; rings; fields; irreducible polynomials; program package PARI/GP; acceleration of the algorithm; comb methods
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:417776
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2022-11-03 10:41:18