Razcep polinomov nad končnimi poljiPapič, Magda (Avtor) Malnič, Aleksander (Mentor) Kuzman, Boštjan (Mentor) polinomOsnovni 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.20162016-05-27 04:05:22Diplomsko delo83102COBISS_ID: 11016009sl