Az előadás helye és ideje: DT 00-112, kedden 8.30-10.00
Számonkérés: a tárgyat szóbeli vizsga zárja. A vizsga helye DT 2.206, a vizsga idelye a Neptumban meghirdetett időpontokban, illetve egyéni megbeszélés szerint. A vizsgán szereplő tételek.
R. Lidl, H. Niederreiter: Finite fields
Járai Antal: Bevezetés a matematikába
Kiss Emil: Bevezetés az algebrába
1. előadás, 2012.09.11: Test, ferdetest fogalma, Wedderburn tétele, bővítés fogalma, test vektortér részteste fölött, bővítés foka, algebrai ill. transzcendens elem, minimálpolinom és annak tulajdonságai, elem foka, véges bővítés algebrai.
2. előadás, 2012.09.18: Elmaradt.
3. előadás, 2012.09.25: Testbővítések konstrukciója, kommutatív egységelemes gyűrű maximális ideálja szerinti faktorgyűtű test, Euklidészi gyűrűk főideálgyűrűk, maximális ideálok főideálgyűrűkben, testbővítésnek létezése, melyben egy irreducibilis polinomnak van gyöke, ill. melyben egy tetszőleges polinom faktorokra bomlik, felbontási test fogalma.
4. előadás, 2012.10.02: Testbővítések: felbontási test egyértelműsége. Véges testek: karakterisztika, nullosztómentes gyűrű karakterisztikája, prímtest fogalma és létezése, véges testek elemszáma, résztest elemszáma, véges testek karakterizációja (létezésük és egyértelműségük).
5. előadás, 2012.10.09: Frobenius automorfizmus. Véges test additív és multiplikatív csoportja. Diszkrét logaritmus fogalma és alapvető tulajdonságai. Kriptográfiai alkalmazások: Diffie-Hellman kulcscsere protokoll, ElGamal titkosítás és digitális aláírás.
6. előadás, 2012.10.16: Index kalkulus. Véges test feletti polinomok: adott fokú ireducibilis főpolinomok szorzata, egyenlet a n-ed fokú irreducibilis polinomok számára, Möbius függvény, Möbius inverziós formula, n-ed fokú irreducibilis polinomok száma, ill. létezésük.
7. előadás, 2012.11.06: Véges testek fölötti polinomok faktorizációja, Berlekamp algoritmus. Elem nyoma véges tesben, a nyom alapvető tulajdonságai. Nyom és lineáris leképzések kapcsolata.
8. előadás, 2012.11.13: Nyom magja. Norma és alapvető tulajdonságai. Polinomok gyökeinek keresése kis prímtestben, nagy prímtestben és kis karakterisztikájú nagy testben.
9. előadás, 2012.11.20: Polinomok gyökeinek keresése kis karakterisztikájú nagy testben (folyt.). Lineáris rekurzív sorozatok. Periódikus sorozatok, küszöbszám, minimális periódus, a minimális periódus hossza osztja az összes periódus hosszát. Véges test fölött minden lineáris rekurzív sorozat periódikus. Elégséges feltétel, hogy a küszöbszám 0 legyen. A sorozatot generáló mártix, és kapcsolata a sorozat minimális periódus hosszával.
10. előadás, 2012.11.27: Lineáris rekurzív sorozatok. Inhomogén sorozatok. IRS (impulse response sequences) fogalma. IRS periódusa, annak kapcsolata a generáló mátrixhoz. Lineáris rekurzív sorozat és a hozzá tartozó IRS minimális periódusának kapcsolata. Tisztán periódikus sorozatok, elégséges feltétel a tisztán periódikusságra. Rekurzió karakteriszikus polinomja, annak kapcsolata a generátor mátrixszal. Lineáris rekurzív sorozatok előállítása zárt formulával.
11. előadás, 2012.12.04: Lineáris komplexitás fogalma. Explicit inverz generátor és annak lineáris komplexitása. A sorozat kezdőszeleteinek lineáris komlexitása közötti kapcsolat.
12. előadás, 2012.12.11: Lineáris komplexitás (folyt.). Sorozatok lineáris komplexitásának kiszámolása a Berlekamp-Massey algoritmussal. Legendre és Jacobi szimbólum fogalma, és alapvető tulajdonságaik. Kvadratikus maradékok, nem-maradékok és pszeudo-maradékok. Kvadratikus pszeudo-maradékok problémája. Goldwasser-Micali titkosítás.