Razcep polinomov nad končnimi polji

Papič, Magda (avtor), Malnič, Aleksander (mentor), Kuzman, Boštjan (mentor)

Osnovni izrek algebre pove, da lahko vsak nekonstanten polinom s koeficienti iz polja kompleksnih števil razcepimo na produkt linearnih členov s koeficienti v istem polju. To pa ne velja za številna druga, prav tako pomembna in zanimiva polja, kot so denimo končna polja. Vsa končna polja, ki obstajajo, so reda q=pk, pri čemer je p praštevilo, k pa element naravnih števil. Poljubni končni polji istega reda sta si izomorfni, zato je polje reda q enolično določeno. Imenujemo ga Galoisovo polje, po francoskem matematiku Evaristu Galoisu (1811-1832). Diplomsko delo obravnava razcep polinomov nad takimi polji. V splošnem velja, da nekateri polinomi višjih stopenj niso razcepni, vendar pa ima vsak polinom s koeficienti v polju enoličen razcep na nerazcepne faktorje. Za končna polja so znani različni algoritmi, ki ugotovijo razcepnost oziroma nerazcepnost polinoma in razcep tudi poiščejo, če ta obstaja. Eden izmed takih algoritmov je tudi Berlekampov algoritem, ki si ga v diplomskem delu podrobno ogledamo. V uvodnem poglavju orišemo zgodovinski razvoj obravnavanega problema in nekaj sodobnih zgledov uporabe. V drugem poglavju predstavimo osnovne pojme in lastnosti algebrskih struktur ter nekaj klasičnih rezultatov, ki so nujno potrebni za razumevanje algoritma. To so grupe, kolobarji, polja, kvocientni kolobarji in kolobarji polinomov. Algoritem uporablja tudi Kitajski izrek o ostankih za polinome in Evklidov algoritem za računanje največjega skupnega delitelja dveh polinomov. V osrednjem razdelku najprej prikažemo štiri naivne metode za iskanje razcepa polinoma. Pri vsaki metodi navedemo najprej zgled razcepa polinoma z realnimi koeficienti nato pa še zgled razcepa polinoma s koeficienti iz končnega polja. Pri metodi sita denimo sproti sestavljamo seznam nerazcepnih polinomov nizke stopnje. Nerazcepne polinome do vključno stopnje šest nad končnimi polji Z2, Z3, Z5 in Z7 izračunamo po tej metodi s pomočjo lastne kode v programskem jeziku VisualC#. Naivnim metodam sledi podroben opis Berlekampovega algoritma z izreki, dokazi in različnimi zgledi. Na koncu razdelka prikažemo tudi lastno implementacijo algoritma v algebrskem orodju MAGMA.

• Jezik: Slovenski jezik
• Ključne besede: polinom
• Vrsta gradiva: Diplomsko delo
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: PEF - Pedagoška fakulteta
• Leto izida: 2016
• PID: 20.500.12556/RUL-83102
• COBISS.SI-ID: 11016009
• Datum objave v RUL: 24.08.2016

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Factorization of polynomials over finite fields

Izvleček

The fundamental theorem of algebra states that every non-constant polynomial with complex coefficients can be factorized on linear factors with coefficients from the same field. However, this is not true for numerous other equally important and interesting fields such as, for example, finite fields. All existing finite fields are of the q=pk order, where p is a prime number and k is a positive integer. Any two finite fields of the same order are mutually isomorfic, therefore the field of q order is unique; it is also known as »the Galois field«, named after the French mathematician Evariste Galois (1811-1832). This thesis deals with factorization of polynomials over finite fields. The general rule states that some polynomials are not reducible, yet each polynomial with coefficients of the field can be uniquely factorized into irreducible factors. There are various known algorithms that can determine whether or not a polynomial is reducible and – in the case of reducible polynomials – also find this factorization. There are several such algorithms, however, this thesis shall focus on the Berlekamp's algorithm. The introductory chapter introduces the historical development of the various approaches to polynomial factorization and presents some modern applications that are currently in use. The second chapter focuses on basic concepts and characteristics of algebraic structures and some classic results that are crucial for the understanding of the algorithm (e.g. groups, rings, fields, division rings and polynomial rings.). The algorithm also uses the Chinese remainder theorem for polynomials and Euclidean algorithm for calculating the greatest common divisor of two polynomials. The first part of Chapter 3 (i.e. the main chapter of the thesis) demonstrates 4 naive methods for the finding of polynomial factorization. For each of the methods we first introduced factorization of a polynomial over real numbers and then continued with an example of a polynomial with coefficients in the finite field. The sieve method, for instance, builds a list of irreducible polynomials of low degrees. Irreducible polynomials up to (and including) degree 6 over the finite fields Z2, Z3, Z5 and Z7 can be calculated using our own code made in the VisualC# programming language. These naive methods are followed by a detailed description of the Berlekamp's algorithm with theorems, proofs and various examples. At the end of section we present our implementation of the algorithm in the computational algebra system MAGMA.

• Ključne besede: polynomial