Matematika | Diszkrét Matematika » Dr. Tóth Mihály - Algebra a számítástudomány matematikai alapjai c. tárgyhoz

Algebra a Számítástudomány matematikai alapjai c. tárgyhoz Írta Dr. Tóth Mihály főiskolai tanár Székesfehérvár, 2002 január 1 Az „algebra” szó eredete az arab „al-jabr” szó, amely összeilleszkedést, újra-egyesítést jelent. Ennek a szónak az első matematikai értelmezése valószínüsíthetően Muhammad ibn Musa al-Kharizmi arab matematikustól származik a IX századból Ő írta az első ismert algebra könyvet és neki tulajdonítják, hogy a nyugati világ figyelmét felhívta az arab számokra. 1 Azóta az algebra a matematikai igen sok olyan fejezetének közös gyüjtőneve lett, amelyek objektumok diszkrét halmazaira, azok manipulálására és elemzésére koncentrálnakEzek a fejezetek magukba foglalják az elemi absztrakt algebrát, a lineáris algebrát, az algebrai geometriát és az algebrai topológiát. A kódoláselmélettel foglalkozó kutatók első generációja a már az akkor is rendelkezésre álló matematikai eszközöknek

csak igen kis részét használta az első hibajavító kódokhoz. A Hamming kódok megértéséhez pl elegendő mind a lineáris algebra, mind a kombinatorika nagyon felületes ismerete is. 2 Egy kicsit többre van szükség a ciklikus és a Reed-Müller kódokhoz. A Reed-Solomon és a BCH kódoknak az előbbiektől független kifejlesztése azonban jelentősen mélyebb algebrai eszközkészletet igényelt. Ezzel együtt viszont az eredményül kapott kódok teljesítménye is igen jelentősen megnövekedett Ez a tendencia aztán egészen az 1990-es évekig egyre erősödött pl azzal, hogy az igen jó és hosszú blokk-kódok konstrukciójához az algebrai geometriát alkalmazták. (Ilyen kódokat használnak pl a CD technikában) Ebben az írásban az algebrai csoportok, véges testek, a vektorterek és a Galois testek algebrai fogalmait foglaljuk össze. Ez az ismeretanyag jó alapot ad a blokk- és a konvolúciós kódok általános elméletének a megértéséhez. Ezek mellett

(remélhetően) érthetőbbé tesz bizonyos blokk-kódokat, mint amilyenek pl a Hamming kódok, a ciklikus kódok és a Reed-Müller kódok. Ugyanezek az algebrai ismeretek (matematikailag) megalapozzák az Információ titkosítása c. studiumot is, különösen annak az aszimmetrikus kriptográfiával foglalkozó fejezetét. Jól használhatók továbbá a diszkrét időben vizsgált rendszerek elvi alapjaihoz is 3 1 Az un . ar ab s zámok t ulajdonképpen I ndiából s zármaznak Al K hwarizmi s zámos szanszkrit nyelvű matematikai írást fordított arab nyelvre. Ezeket a munkákat később latinra fordították és így lehetővé vált a megismerésük a nyugati világ számára is. Későbbi fejlemény, hogy alKhwarizmi nevéből származik az „algoritmus” szó is Ha manapság valaki Egyiptomba, vagy más, arabul beszélő országokba látogat, meglepődhet azon, hogy mennyire különböznek az arab írás számjegyei az E urópában használatos „arab”

számjegyektől. Érdekes azonban, hogy míg az arab szövegírás jobbról balra (vagy soronként váltott irányban) történik, a szövegbe iktatott többjegyű számokat mindíg balról jobbra kell olvasni. 2 Ezt kihasználva heurisztikus alapon adtunk némi betekintést korábban „A hibavédelmi kódolás és áramkörök” c. jegyzet kiegészítésben (Dr Hudoba György és Dr Tóth Mihály; kandó-SzGTI 1990) az itt tárgyalt témakörbe. Mivel az absztrakt algebrai alapok némi ismerete ma már nem csak a k ódoláselmélethez, hanem –többek között- a kriptográfiához is nélkülözhetetlen, ezért döntöttünk úgy, hogy ebben az anyagban összefoglaljuk a legfontosabb fogalmakat. 3 Rendszerelmélet, Algoritmusok elmélete, Formális nyelvek, Digitális rendszertechnika. 2 1 Algebrai struktúrák és műveletek. Egy halmaz valamilyen objektumok, elemek tetszőleges gyűjteménye és előzetesen az égadta világon semmilyen műveletet nem definiálunk a

halmaz elemei között. A halmaz lehet véges ( pl. a székesegyházak halmaza Magyarországon), lehet megszámlálhatóan végtelen (mint pl a pozitív egészszámok halmaza), vagy megszámlálhatatlanul végtelen (mint pl az összes valós számok halmaza) Egy halmaz elsőrendűen fontos jellemzője a halmaz számossága (kardinalitása), amely definició szerint a halmazba tartozó objektumok számát jelenti. A helyzet akkor válik bonyolultabbá, amikor a halmaz tetszőlegesen kiválasztott két eleme (=argumentumok vagy operandusok) között valamilyen műveletet definiálunk 4, amelynek az eredménye olyan objektum, ami vagy beletartozik ugyanabba a halmazba, amelyből a művelet két argumentumát kiválasztottuk, vagy nem. A kétargumentumos műveleteket bináris műveleteknek is szokták nevezni, de nem azért, mert a műveletet bináris számokon hajtjuk végre, hanem azért, mert a művelet két operandus között van értelmezve. Művelet, reláció, zártság,

művelettábla, kommutativitás, particionálás, 4 Ezt úgy mondjuk, hogy a halmaz felett egy műveletet definiálunk. 3 Álljunk meg egy szóra a művelet (és a relációk) fogalma kedvéért! A két operandus között értelmezett művelet itt teljesen általános fogalom. A halmaz, amely felett a műveletet definiáljuk, az adott műveletre nézve zárt, ha a művelet eredménye i s a halmazba t artozik, akármilyen el emei i s a h almaznak az o perandusok. A kétargumentumos műveletet művelettáblával lehet definiálni. Jelentse például a körplusz művelet (csak itt és csak most) a mod 3 összeadást és értelmezzük a {0,1,2} háromelemű halmaz felett. (A „közönséges” összeadás eredményét 3-mal kell osztani –ha nagyobb 3-nál- és a művelet eredménye ennek az osztásnak a maradéka lesz.) A művelettábla ekkor a következő: ⊕ 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 Az itt példaként definiált körplusz művelet történetesen kommutatív s

ilyenkor a művelettábla a főátlójára szimmetrikus. Ne tévesszük össze a halmaz elemei felett értelmezett műveletet a halmaz elemeinek viszonyát kifejező relációval. A r eláció –ha egyáltalán értelmezhető a halmazon- mindíg k ét el em viszonyát fejezi k i. P l a zt, h ogy az egyik elem nagyobb, mint a másik, vagy egyenlőek egymással, s tb. A < és a≤ ill a > és a ≥ relációk a halmaz elemeit sorba rendezik, az egyenlőség (= ekvivalencia) reláció pedig diszjunkt részhalmazokba osztja a halmaz elemeit, más szóval particionálja az alaphalmazt, de ezekről később majd még lesz szó. A művelet és a reláció, mint leképezés Zártnak mondunk egy kétargumentumos műveletet akkor, és csakis akkor, ha a művelet eredménye is abba a halmazba tartozik, amelyből az argumentumait (=operandusait) vettük. Jelöljük ezt az „alaphalmazt” A-val és az elemeit ai-vel ill. aj-vel. Egy kétargumentumos műveletet az A halmazból vett ai

és aj elemeken, tehát az (ai, aj) rendezett elempáron hajtunk végre és a zártsági feltétel miatt a művelet ak eredményének is az mazható, hogy az A halmaz elemei közé kell tartoznia. Mindez úgy is megfogal- A halmaz önmagával alkotott direkt szorzatát a művelet leképezi magára az A halmazra, azaz AXA⇒A A zárt művelet tehát semmi esetre sem mutathat a halmazon kívülre. Azt állítottuk, hogy a reláció egy halmaz elemei közötti viszonyt fejezi ki és éppen ebben különbözik a művelettől, mint olyantól. Nos, ez így is van Mindezek mellett azonban a reláció is értelmezhető egyfajta leképezésként. 4 Az ai, aj ∈ A halmaz-elemek közötti viszony (=reláció) is értelmezhető az A X A szorzathalmazra, azaz az (ai, aj) rendezett elempárokra, de e két elem viszonyát valami olyasmi fejezi ki, ami az A alaphalmaznak nem eleme. Lényegében egy R binér reláció az A X A direkt szorzat részhalmaza. Fel lehet sorolni azokat a párokat,

amelyek relációban vannak egymással. R⊂AxA. ai lehet nagyobb vagy kisebb, mint aj , vagy éppenséggel lehetnek egyenlők (ekviva- lensek) is. Az A halmaznak azonban nem elemei a „nagyobb”, a „kisebb”, vagy az „egyenlő” jelek 5 és általában egy elempár viszonyát kifejező jelek, megnevezések. A relációk esetében tehát a szorzathalmaz olyan A XA⇒ℜ leképezéséról van szó, amely tipikusan az A alaphalmazon kívülre mutat. Az A halmaz ai, aj elempáron értelmezett reláció vagy teljesül (=IGAZ) vagy nem (=HAMIS). Az algebrai struktúra és a műveletek Egy halmazt és a felette értelmezett műveletet, vagy műveleteket együtt gyüjtőnéven algebrai struktúrának nevezzük. Ugyanazon halmaz felett egy, vagy több művelet is definiálható. Az alábbiakban először egyműveletes, majd két- és több-műveletes algebrai struktúrákról lesz szó Ha egy halmaz felett két műveletet definiálunk, akkor az egyiket szokás additív

műveletnek, a másikat pedig multiplikatív műveletnek nevezni, elvileg teljesen függetlenül attól, hogy bármi közük lenne akár az összeadáshoz (=addició), akár a szorzáshoz (=multiplikáció). Ezeknek az elnevezéseknek csak annyi a hasznuk, hogy a szövegben a műveleti jel nélkül, a művelet elnevezésével tudunk hivatkozni a két művelet közül az egyikre ill. a másikra. 6 Ha egy algebrai struktúra felett csak egy művelet van értelmezve, s az adott egyműveletes struktúrát történetesen csoportnak nevezzük 7, akkor a műveletet az adott csoport un. csoport-műveletének nevezzük 8, és jóllehet semmi okunk rá, hogy akár 5 Természetesen ezeken kívűl még más, sokféle reláció is létezik. 6 Látni fogjuk később, hogy ezek az elnevezések mégis csak jellemzőek lesznek az adott struktúráknál definiált műveletekre, mert praktikus okokból éppen valamiféle s peciális ö sszeadás i ll. szorzás jellegű műveleteket fogunk bevezetni.

Ez azonban csakis „úri kedvünktől” függ és nem valamiféle elmélet követelménye. 7 Alább definiáljuk majd az algebrai csoport fogalmát. 8 Ha csak egy műveletet definiálunk a halmaz felett, akkor semmi okunk sincs arra, hogy azt akár additívnak, akár multiplikatívnak nevezzük, mivel nincs másik művelet, amelytől meg kellene 5 additívnak nevezzük, akár pedig multiplikatívnak, mégis alkalmazni szokták rá az „additív” jelzőt s ezért szokás additív csoportról beszélni. Az algebrai csoportnál ez tényleg csak kényelmi szempont, azonban a testeknél már lényegesebb, hiszen magáról a számtestekről is szó van. Az analógia ezért van A művelethez tartozó egységelem és zérus elem. Mindig az éppen vizsgált művelethez tartozó egységelemet és zérus elemet szokás definiálni. Válasszuk itt és most műveleti jelnek a körbe írt csillagot: műveletet körcsillag műveletnek. ⊛: AxA  A ⊛ és nevezzük a Ha (az

egyébként tetszőleges, de zárt) körcsillag műveletre igaz, hogy az alaphalmaz bármely a ∈ A , e ∈ A és z ∈ A elemére a⊛e=e elem. A ⊛ a = a minden a ∈ G. Ez az e elem a ⊛ művelethez tartozó egység- és ha a ⊛ z = z ⊛ a = z minden a ∈ G. Ez a z elem a elem. (Ezt neutrális elemnek is szokták nevezni) ⊛ művelethez tartozó zérus- P 1 Példa A hétköznapi aritmetikai gyakorlatból ismert szorzás műveletének egységeleme az 1 és zérus-eleme a 0, mert a.0 =0a = 0 és a1 =1a = a (vö a definicióval!) Az ugyancsak a hétköznapi aritmetikából jól ismert összeadási művelet egységeleme azonban a 0, mert a+0 =0+a = a, az összeadás zérus eleme pedig nem létezik. Az inverz elem. Ha minden a ∈ A hez létezik egy (és csakis egy) olyan a-1 elem A-ban, amelyre igaz, hogy a ⊙ a-1 = a-1 szerinti inverz eleme. ⊙a= e, akkor az a-1 az a elemnek a körpont művelet Jegyezzük meg! Az egységelem, a zérus-elem és az inverz elem

mindíg valamilyen művelttel kapcsolatban értelmezhető és definiálható és csakis arra a műveletre érvényes. különböztetnünk. Egyműveletes struktúráról van szó, és kész A művelet pedig a csoport művelete = csoportművelet. 6 Semmi szokatlan nincs abban, hogy ha egy algebrai struktúrában több műveletet definiálunk, akkor mindegyik műveltre más-más egységelem és zérus elem határozható meg. A műveletek (kitüntetett) tulajdonságai. Egy a fentiekben részletesen körülírt, A halmaz feletti műveletnek számos tulajdonsága lehet, de ezek között van néhány (kitüntetett) tulajdonság, amelyeknek külön nevet is adtak. Ilyen volt pl a zártság, ami azt jelentette, hogy egy velet eredménye is az A halmaz eleme. A halmaz felett értelmezett mű- Kommutatív a művelet, ha az argumentumai felcserélése esetén is ugyanaz a művelet eredménye. Képletben: Ha a,b,c ∈ A és a ⊛ b = b ⊛ a = c akkor, és csakis akkor a ⊛ művelet

kommutatív. A kommutativitás egyébként a művelettáblából is kitűnik, mert ekkor a (bináris) művelettábla a főátlójára szimmetrikus. Ez fordítva is igaz: Ha egy művelettábla nem szimmetrikus a főátlójára nézve, akkor az azzal definiált művelet nem kommutatív. A kommutativitás fogalma kettőnél több argumentumos műveletekre is kiterjeszthető. P 2 Példa: A „hétköznapi” aritmetikai műveletek közül mind az összeadás, mind a szorzás kommutatív, mert az összeadandók ill. a tényezők sorrendje nem befolyásolja a művelet eredményét. Asszociatív a művelet, ha kettőnél több argumentum (=operandus) esetén független az eredménye attól, hogy hogyan csoportosítjuk az argumentumokat. (Ti azok sorrendjének megváltoztatása nélkül.) Képlettel kifejezve: A ⊛ művelet asszociatív, ha minden a,b,c ∈ A-ra (a ⊛ b ) ⊛c=a⊛(b⊛c) azaz a végeredmény független attól, hogy mely elempárra (vagy párokra) végezzük el először

a ⊛ műveletet. A disztributivitás két művelet egymáshoz képest fennálló viszonyára értelmezhető. Vezessünk be itt egy újabb művelet-jelölést, nevezetesen az un. körplusz műveletet: ⊕ (és egyelőre egyáltalán nem is érdekes, hogy ezt milyen művelettábla definiálja. A lényeg csak az, hogy különbözik a ⊛ művelettől.) 7 Disztributív a ⊛ művelet a ⊕ művelet felett, ha minden a, b, c ∈ A-ra igaz, hogy a ⊛ (b ⊕ c) = (a ⊛ b) ⊕ (a ⊛ c) P 3 Példa: A mindennapok aritmetikájában a szorzás disztributív az összeadás felett. Disztributív a ⊕ művelet a ⊛ művelet felett, ha minden a, b, c ∈ A-ra igaz, hogy a ⊕ (b ⊛ c) = (a ⊕ b) ⊛ (a ⊕ c) Ez viszont a mindennapok aritmetikai műveleteinél már nem igaz. Érdekes azonban megjegyezni, hogy a Boole algebrában bármelyik duális műveletpárra igaz, hogy az egyik művelet disztributív a másik felett. (Éppen emiatt érvényesek az un de Morgan tételek és a

dualitás elve) Idempotens egy tetszőleges ⊛ művelet, ha minden a ∈ A-ra igaz, hogy a ⊛ a = a Megjegyzések: A felsorolt műveleti tulajdonságok ―az idempotenciát kivéve― egymást, tehát szimultán is értelmezhetők. nem zárják ki Ahhoz, hogy egy kétargumentumos műveletet (értelmesen) értelmezni tudjunk egy halmaz felett, a halmaznak legalább 2 eleme kell, hogy legyen. Ez azonban nem elvi követelmény, tehát általános esetben vizsgálni lehet és kell is az egyelemű halmazokon értelmezett kétargumentumos (= bináris) műveleteket is. 8 A műveletek tulajdonságainak összefoglalása Asszociativitás: ∀ a ∀ b ∀ c –re: (a ⊛ b) ⊛ c = a ⊛ (b ⊛ c) Kommutativitás: ∀ a ∀ b–re: a ⊛ b = b ⊛ a Idempotencia: ∀ a–ra: a ⊛ a = a Disztributivitás 9: ∀ a ∀ b ∀ c –re: a⊛(b ⊠ c) =(a⊛b) ⊠ (a⊛c) Egységelem 10 létezése: ∀ a –ra ∃ e : (a⊛e) = (e⊛a) = a Invertálhatóság: ∀ a ∀ b–ra ∃ x

∧ ∃ y : x⊛a = b ∧ a⊛y = b Inverz elem létezése: ∀ a –ra ∃ a-1 : a ⊛ a-1= e ∧ a-1⊛ a = e 9 Nem egy művelet jellemzője, hanem két művelet viszonyára vonatkozik. Azt mondjuk, hogy az egyik (itt ⊛)disztributív a másik (itt ⊠ )felett, de fordítva ez általában nem igaz. 10 ezt néha neutrális elemnek is mondják. 9 2 Egyműveletes algebrai struktúrák. D 1 definició: Az algebrai struktúra Egy nem üres halmazt és a felette értelmezett egy, vagy több műveletet együttesen algebrai struktúrának nevezzük. 11 Ebből az alap-definicióból több más definició ill. fogalom is származtatható A származtatás során az alaphalmaz változatlan, és aszerint nevezzük el az újabb és újabb struktúrákat, hogy milyen tulajdonságokat teszünk kötelezővé a halmaz felett értelmezett műveletre (vagy műveletekre) nézve. D 2 definició: A félcsoport 12 Amikor egy alaphalmazt és a felette értelmezett egy kétargumentumos műveletet

tekintjük, akkor az így kapott algebrai struktúrát félcsoportnak nevezzük akkor, és csak akkor ha a művelet a következő tulajdonságokkal rendelkezik: zárt asszociatív (más kikötés nincs.) Magát a műveletet akármilyen, tetszőlegesen választott műveleti jellel jelölhetjük. Kétműveletes struktúrára is értelmezhetjük ezt, és az alábbi származtatott fogalmakat a következőképp: Legyen a kétműveletes algebrai struktúra egyik művelete a körplusz ( más megnevezéssel: additív) művelet, a másik művelete pedig a körpont (más megnevezéssel: multiplikatív) művelet. 11 A nem üres halmaz elvileg egyetlen elemet is tartalmazhat és egyetlen elemre is definiálható kétargumentumos művelet. (Persze a két operandus ekkor azonos és az eredmény is a halmaz egyetlen eleme, ha a művelet zárt.) Ennek a triviális esetnek azonban az alábbiakban semmilyen gyakorlati értelme nincs, ez ért c sakis olyan hal mazokkal f oglalkozunk, am elyeknek l

egalább két elemük van 12 Angol terminológiával: semigroup. 10 Teljesüljön a zártság mindkét műveletre, de az asszociativitás, mondjuk, csak az additív műveletre. Ekkor azt mondhatjuk, hogy az adott struktúra az additív műveletére nézve félcsoport, a multiplikatív műveletére nézve viszon nem az Az alaphalmaz és (itt) az additív művelet változatlanul algebrai struktúra, de emellett eleget tesz egy szűkebb fogalomnak is, azaz egyúttal félcsoport is. Figyeljünk arra, hogy a félcsoport jelleget csak az adott esetben figyelembe vett művelet tulajdonságai határozzák meg, és (itt) egyszerre csak egy műveletet kell figyelembe venni akkor is, ha az alaphalmaz felett több művelet van értelmezve D 3 definició: A csoport 13 Amikor egy alaphalmazt és a felette értelmezett egy kétargumentumos műveletet tekintjük, akkor az így kapott algebrai struktúrát csoportnak nevezzük de csak akkor, és csakis akkor ha a csoportművelet a következő

tulajdonságokkal rendelkezik: zárt asszociatív van egységeleme és definiált benne az inverz elem is. 14 Lényeges azonban, hogy minden elemre teljesüljön, azaz ∀a∈A-ra ∃a-1 Magát a műveletet akármilyen, tetszőlegesen választott műveleti jellel jelölhetjük. A csoportműveletre több megkötés érvényes, mint a félcsoport esetén. A zártság minden algebrai struktúrára előírás, az asszociativitás (a zártság megtartása mellett) csak a félcsoportra, és az inverz elem létezése (az előbbi feltételek megtartása mellett) csak a csoportra. Tulajdonképpen nem kell az egységelem létezését külön feltételnek tekinteni, mert az inverz elem fogalmában már benne van. Az inverz elem ugyanis csakis az egységelem segítségével értelmezhető (Ld a korábbi „inverz elem” definiciót) Az inverz elem megléte azt is jelenti, hogy a műveletnek létezik az inverze is. A csoportművelet esetén is értelemszerüen igaz az, amit a félcsoportnál már

elmondtunk. Nevezetesen előfordulhat, hogy egy kétműveletes algebrai struktúra az egyik (mondjuk az additív) műveletére nézve csoport, a másik (multiplikatív) műveletére nézve padig félcsoport. 13 Angol t erminológiával a h almaz: s et, a c soport pedig: gr oup, ezért az utóbbit G -vel szo kták jelölni. Ezt a jelölést mi is megtartjuk és alkalmazzuk 14 Az inverz elem definiciója csakis úgy értelmezhető, ha létezik a műveletre vonatkozó egységelem. Az inverz és az egységelem tehát kölcsönösen feltételezik egymást 11 D 4 definició: Az Ábel csoport15 Ha a csoportművelet kommutatív, akkor a csoportot Ábel csoportnak nevezzük. Az Ábel csoportok esetében a csoportműveletre szokásos a ⊕ (körplusz) műveleti jelet alkalmazni és magát a csoportot additiv csoportnak nevezni. 16 A fenti definiciók családfáját a következő oldalon egy összefoglaló ábrán is szemléltetjük. Az ábrán ugyan csak • az egy- és a

kétműveletes struktúrákat tüntettük fel, és • a családfának csak az egyműveletes struktúrákkal kapcsolatos utódjait szemléltettük talán mégis segíti az összefüggések megértését. Jegyezzük meg azonban, hogy • Mind egy- mind többműveletes struktúrák léteznek és az utóbbiak nem csak a kétműveletes struktúrákat jelentik • Léteznek a vázoltaknál komplexebb struktúrák is. Pl olyanok, amelyek nem egy alaphalmazra épülnek, hanem pl. egy „F” kétműveletes struktúrára (annak alaphalmazát és két „saját” műveletét beleértve) továbbá egy második „V” halmazra úgy, hogy az „F” struktúra és a „V” halmaz elemei között is definiálunk műveletet. A továbbiakban majd foglalkozunk is egy ilyen komplex struktúrával, amelyet vektortérnek nevezünk és a hibavédelmi kódok matematikai modellezésekor lesz különösen fontos jelentősége. 15 Az angol terminológia szerint: Abelian group 16 Tekintettel arra,

hogy a csoportműveletre nincs előírva a művelet kommutativitása, de esetenként a művelet kommutatív is lehet, ezért –ha a művelet kommutatív- jogos a „kommutatív csoport” megnevezés. A kommutatív műveletes csoportoknak külön nevük is van: Ábel csoport A „kommutatív jelzőnek tehát van releváns j elentése. A z Á bel c soportot néha „ additív csoportnak” is nevezik. Jóllehet az összeadás valóban kommutatív művelet, de nem minden kommutatív művelet összeadás, tehát tulajdonképpen logikátlan a kommutatív (Ábel) csoportot additív csoportnak nevezni. 12 13 Példák a csoportokra P 4 Példa Az egészszámok végtelen halmaza felett értelmezett összeadás művelete az egészszámok halmazával együtt kommutatív csoportot (tehát Ábel csoportot) alkot. (Mert az összeadás kommutatív művelet.) Ügyeljünk arra, hogy nem a természetes számokról van szó, mert kell, hogy minden pozitív egészszámnak létezzen az inverze is,

s ez pedig a vele azonos abszolut értékű negatív egészszám. A negatív számok viszont nem tartoznak a természetes számok halmazába. Az itt hivatkozott negatív egészek a csoportműveletre vonatkozó inverzek. Ha a csoportműveletet additív műveletnek nevezzük (ami itt teljes mértékben indokolt, hoszen az összeadásról van szó) akkor a negatív egészek az additív inverzek. Mivel az inverz elem létezik, az összeadási művelet inverze is létezik. Ezt nevezzük kivonásnak. Az adott esetben létezik a csoportműveletre vonatkozó egységelem is a halmazban. Az összeadás egységeleme a 0, mert bármely a ∈ A-ra igaz, hogy a + 0 = 0 + a = a (ami éppen az egységelem definiciója) Az adott esetben az egységelem érdekes reprezentációja a számegyenesen kijelölt 0 pont, ami bármely a szám esetén a hozzátartozó a-1 inverz elem tükrözési pontja. Az összeadás művelete esetében viszont nincs egyetlen zérus elem. Azaz nincs olyan kitüntetett egész

szám, amelyet bármely egész számhoz hozzáadva ezt a kitüntetett egész számot kapnánk eredményül. P 5 Példa A mindennapi értelemben vett szorzás nem lehetne az egészszámok halmaza feletti csoportművelet, mert a szorzás inverzei racionális törtek lennének, amelyek nem tartoznak az egészszámok körébe. Ha azonban a pozitív racionális számok végtelen halmaza felett értelmezzük a szorzás műveletét, akkor szintén Ábel csoportot kapunk, amely Zárt Asszociatív, mert több tényező esetén mindegy, hogy milyen párosításban szorozzuk össze a tényezőket. A pozitív racionális számok körében minden a számnak létezik az inverze, azaz 1/a is. Az inverz létezésének a következménye, hogy létezik az inverz művelet, vagyis az osztás is és annak az eredménye is a pozitív racionális számok körébe tartozik. Mivel az inverz elem létezik, léteznie kell az egységelemnek is, amelyre igaz, hogy azzal (mármint az egységelemmel) bármely a

számot megszorozva magát az a számot kapjuk eredményül. A szorzás egységeleme az 1. A racionális számok felett értelmezett szorzás esetében nem értelmezhető a 0, mert annak nincs inverze, mivel 0-val nem lehet osztani. 14 Figyeljünk fel arra, hogy az algebrai struktúrák eddig leírt családfájában a zérus elem létezése sehol sem volt kikötve. Mivel a szorzás kommutatív így Ábel csoportról van szó. A pozitív racionális számok halmaza és a felette értelmezett szorzás tehát olyan algebrai struktúrát alkot, amely csoport, sőt: Ábel csoport. P 6 Példa Az nxn-es, reális elemekből álló, négyzetes mátrixok halmaza a mátrix összeadásra, mint csoportművetre nézve kommutatív csoportot, azaz Ábel csoportot alkot. Ha nem négyzetes mátrixok szorzásáról lenne szó, akkor az nxk elemű mátrix ugyan szorozható lenne a kxn elemű mátrixszal (k ≠ n), de több, nem négyzetes mátrix esetén már egyáltalán nem biztos, hogy a

tényező mátrixok minden kombinációjában végrehajtható lenne a szorzás, és még két tényező esetén sem, ha azokat felcserélnénk. A művelet így sem nem asszociatív, sem nem kommutatív Azonos rangú (nxn-es) mátrixok esetén –és csakis ebben az esetben- mind az asszociativitás, mind a kommutativitás feltétele teljesül. D 5 definició: Egy csoport rendje Definició szerint egy csoport rendje azonos annak kardinalitásával, vagyis az alaphalmaz számosságával 17. Meg kell azonban jegyezni, hogy egy csoport kardinalitása egymagában nem elegendő ahhoz, hogy magát a csoportot specifikálja, hacsak előre ki nem kötöttük, hogy mi az a művelet, amelyet figyelembe veszünk 18 A következőkben elsősorban véges csoportokkal foglalkozunk. Ezek elmélete igen gazdag és igen érdekes. Osztályozásuk egyik módja az, hogy feloszthatók-e egyáltalán kisebb csoportokra és ha igen, akkor hogyan A legutóbbi időkig nem felosztható csoportok egyike volt az

un „Szörnyeteg” vagy más néven a „Barátságos óriás”, amely 8 x 1053 elemet tartalmazott. Ezt 1981-ben sikerült RLGriess-nek feldarabolni Ez is és sok más érdekes csoport közvetlen kapcsolatban van a hírközlés elmélettel, a kódoláselmélettel és a titkosítással, de itt a következőkben csak a leginkább hétköznapi csoportokkal foglalkozunk 17 Egy A halmaz számosságának (azaz kardinalitásának) jelölésére szokás a #A jelölést használni. 18 Mivel bármelyik algebrai struktúrát annak alaphalmazán kívül az alaphalmaz felett értelmezett egy, vagy több művelet is meghatározza, persze, hogy nem elegendő a specifikációhoz egyedül az alaphalmaz számossága, hanem a műveletről is tudnunk kell. 15 D 6 definició: A kongruencia reláció Mielőtt a véges csoportokkal foglalkozni kezdenénk, vizsgáljuk meg az un. kongruencia relációt Mivel nem műveletről, hanem relációról van szó, az alaphalmaz egy elempárjának a

viszonyát fejezi ki. Az alaphalmaz most az egészszámok halmaza, beleértve mind a pozitív, mind a negatív egészszámokat és a 0-át is. Ez a számhalmaz megszámlálhatóan végtelen E végtelen számhalmaz ugyancsak végtelen részhalmazokra osztható a maradékos osztás segítségével. Jelöljük az osztót m-mel. Definició szerint az a és a b egészszámok az m osztóra nézve kongruensek, ha mindegyiket külön-külön elosztva m-mel ugyanazt a maradékot kapjuk. Ezt a következőképp jelöljük: a ≡ b mod m 19 Így pl. az m=5 osztóra nézve 11 és 26 kongruensek 11 ≡ 26 mod 5 Érdemes megjegyezni, hogy a kongruencia reláció ekvivalencia tipusú reláció. 20 19 Olvasd: a kongruens b-vel az m modulusra nézve. 20 Ezért az ≡ jel helyett alkalmazhatjuk (és sokszor alkalmazzák is) az = jelet. 16 Álljunk meg egy szóra az ekvivalencia (tipusú) reláció kedvéért! Ekvivalencia tipusú relációról beszélünk akkor, ha a reláció rendelkezik a

következő három tulajdonsággal: 1. Reflexív, azaz bármi ekvivalens saját magával: a≡a 2. Szimmetrikus, azaz ha a ekvivalens b-vel, akkor b is ekvivalens a-val: a≡b⇒b≡a 3. Tranzitív, azaz ha a ekvivalens b-vel b viszont ekvivalens c-vel, akkor szükségképpen igaz, hogy a ekvivalens c-vel: a≡b∧ b≡c⇒a≡c Ha e három tulajdonság közül bármelyik hiányzik, akkor a reláció nem ekvivalencia tipusú. Ekvivalencia tipusú reláció sok van. Ilyen pl a síkháromszögek hasonlósága és ilyen az itt tárgyalt kongruencia reláció is. Az ekvivalencia tipusú reláci egy halmaz elemeit részhalmazokba particionálja. Egy-egy ilyen részhalmazba csak ekvivalens elemek tartoznak és a különböző réshalmazok diszjunktak. E részhalmazokat ekvivalencia-osztályoknak is szokás nevezni. Ellenpéldaként említjük a „kisebb” ( >) vagy a „nagyobb” ( <) relációkat, amelyek esetén az első két feltétel nem teljesül s ezért nem is ekvivalencia

tipusúak. Az ilyen (t.i mint a kisebb vagy nagyobb, stb) relációk rendezik annak a halmaznak az elemeit, amelynek elempárjaira értelmezzük ezeket a relációkat, ezért rendezési relációknak is nevezzük őket. A terminológia szerint egy rendezési reláció reflexív, antiszimmetrikus és tranzitív, azaz az ekvivalencia tipusú relációk három jellemző tulajdonsága közül csak a szimmetria nem teljesedik A kongruencia reláció un. maradékosztályokba csoportosítja az egészszámokat Könnyen belátható, hogy az m osztóval maradékos osztásokat végezve az egészszámokon csak 0, 1, . m-1 maradékokat kaphatunk 21 Ezeket maradékosztályoknak nevezzük és összesen m darab van belőlük Az egészszámokat a következő megfontolás alapján sorolhatjuk be maradékosztályokba: Írjuk fel bármelyik (pozitív vagy negatív) a egészszámot a következő alakban: a = x.m + r 21 Ha t örténetesen n egatív s zámot os ztunk p ozitív os ztóval, ak kor m ind a

há nyados, m ind a maradék n egatív l esz. A maradékosztály-aritmetikában az onban i lyenkor a m aradék abs zolut értéke határozza meg, hogy az osztandó melyik maradékosztályba tartozik.(Ld alább!) 17 ahol a, x ,m és r mind egészszámok. x pedig a maradékos osztás kvóciense (és értékével nem is számolunk a továbbiakban), m a megadott modulus (=osztó) és r a maradék. Ezt az r maradékot –többek közöttarra használjuk, hogy vele „megcimkézzük” a maradékosztályt, amelybe az a egészszám tartozik Ez a „cimke” történetesen kongruens a vele megcimkézett maradékosztály valamennyi elemével, tehát az un. modulo m műveletekben helyettesítheti is a hozzátartozó maradékosztály bármelyik elemét Negatív a szám és pozitív m osztó esetén x is negatív lesz, de ekkor is pozitív maradékot kaphatunk a következő értelmezéssel: r = a – x.m = -| a | + | x |m = | x |m - | a | Pozitív a egészszám esetén tehát olyan x-et kell

találnunk, amellyel az m modulust megszorozva az a-xm=r különbség kisebb az m modulusnál (vagy, legfeljebb, vele egyenlő). Negatív a egészszám esetén olyan (pozitív) x számot kell találni, amellyel az m modulust megszorozva az x.m-|a| = r különbség lesz kisebb, mint az m modulus (vagy, legfeljebb, vele egyenlő). P 7 Példa Az m = 5 modulus maradékosztályaiba sorolható egésszámok r A megcimkézett maradékosztályokhoz tartozó (végtelen) számhalmazok 0 {., -20, -15, -10, --5, 0, 5, 10, 15, 20, } 1 {., -19, -14, -9, -4, 1, 6, 11, 16, 21, } 2 {., -18, -13, -8, -3, 2, 7, 12, 17, } 3 {., -17, -12, -7, -2, 3, 8, 13, 18, 24, } 4 {., -16, -11, -6, -1, 4, 9, 13, 19, 24, } A maradék osztály cimkéje Látható, hogy az m = 5 modulus esetén összesen öt maradékosztály van, és mindegyikbe végtelen sok egészszám tartozik. A maradékosztály „cimkéje” úgy is értelmezhető, hogy az a legkisebb nemnegatív szám az adott maradékosztályba

tartozó végtelen sok egészszám közül. 18 P 8 Példa Az m = 2 modulus két maradékosztályba sorolja az egészszámokat. Az egyik (ti a 0 maradékosztály) a páros számok osztálya, a másik pedig (ti. az 1 maradékosztály) a páratlan számok osztálya. D 7 definició: A modulo m összeadás A modulo m összeadás olyan, véges csoport feletti művelet, amely zárt, tehát az eredménye is a csoport eleme. Asszociatív és kommutatív művelet, tehát egy G halmazzal együtt kommutatív (=Ábel) csoportot alkot Szokás rá úgy hivatkozni, hogy additív (csoport) művelet. (Lásd még alább a T1 tételt is!) Ugyanúgy művelettáblával (is) definiálható, ahogyan bármelyik algebrai művelet. Az egészszámok mindennapi, aritmetikai összeadásától csak abban különbözik, hogy az így számított eredménynek a m modulussal számolt maradéka lesz a mod m összeadás eredménye. Mint az előzőekben láttuk, negatív egészszámokra is értelmezhető. P 9

Példa Jelölje (itt) a mod 7 összeadást a ⊕ szimbólum. Szerkesszük meg a művelettábláját, ha a mod 7 összeadást a G = {0, 1, 2, 3, 4, 5, 6,} halmaz felett értelmezzük. ⊕ 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 2 3 4 5 6 0 2 2 3 4 5 6 0 1 3 3 4 5 6 0 1 2 4 4 5 6 0 1 2 3 5 5 6 0 1 2 3 4 6 6 0 1 2 3 4 5 A művelettábla valamennyi bejegyzése eleme a megadott G halmaznak, ezért a művelet zárt. A művelettábla szimmetrikus a főátlójára, tehát a művelet kommutatív is. A mod 7 összeadási műveletnek van egységeleme és a létezik az inverze is, méghozzá a G halmazon belül. G halmaz minden elemének Melyik az az e elem, amelyre igaz, hogy bármely a ∈ G esetén a ⊕ e = e ⊕ a = a ? 19 Nos, nem nehéz kitalálni, hogy az adott esetben ez a 0, amely –mint illik is neki eleme a G halmaznak. T1. Tétel a mod m összeadásra A q–ad rendű S = {0, 1, 2, 3, . ,q-1} halmaz és a felette értelmezett modulo q összeadási művelet ( ⊕ )

kommutatív (azaz Ábel) csoportot alkotnak. A zártság mindíg teljesül, ha az S halmaznak eleme a 0 is. Az additív műveletnek ez az egységeleme és ha létezik egységelem, akkor minden elemnek van inverze is. A modulo m aritmetika óriási előnye, hogy az egészszámok végtelen halmazát egy véges, m-elemű halmazra képezi le. Látni fogjuk majd pl a nyíltkulcsú titkosításnál, hogy valamennyi gyakorlatban alkalmazható módszernél előfordul a maradékosztály aritmetika. Igaz, hogy a gyakorlatban sohasem dolgozunk végtelen nagy számokkal, de pl. a nyíltkulcsú titkosításnál bizony előfordulnak akár 10200 nagyságrendű számok is, amelyek alkalmazásakor csakis úgy tudjuk elkerülni a túlcsordulást, ha a nagyon nagy számokat leképezzük egy jóval kisebb, maradákosztály-halmazra úgy, hogy maradékosztály-aritmetikát használunk. Ezt a modulo m aritmetika néhány olyan sajátsága teszi lehetővé, amelyeket a következő tételekben fogalmazunk

meg. T 2 Tétel a maradékosztályokra A {0, 1, 2, 3, . , m-1} kongruencia-osztályok a modulo m egész-összeadás alatt egy m-ed rendű kommutatív csoportot alkotnak minden pozitív egész m esetén. Mivel egy maradékosztály bármely két eleme közötti modulo m különbség 0 ezért elegendő, ha a fenti tétellel kapcsolatban csak a cimkék alkotta G = {0, 1, 2, 3, . , m-1} csoportra fordítjuk a figyelmünket, mert az e csoport elemei közötti relációk érvényesek a kongruencia-osztályok közötti relációkra is. Mivel az egészszámok összeadása asszociatív és kommutatív, ezért a modulo m összeadás is asszociatív és kommutatív. Az egységeleme ugyanúgy 0, ahogyan azt már az aritmetikai összeadásnál megmutattuk A G csoporton belül az inverz elem is létezik, mert egy G-beli x szám additív inverze az m-x szám lesz. 20 P 10 Példa: Legyen m=5. Akkor G = {0, 1, 2, 3, 4} Az additív művelet most a modulo 5 összeadás, amit jelöljünk itt ⊕

(körplusz)-szal Nézzük meg, hogy mi lesz x=2 inverze! A mondottak szerint ez x-1 =5-2 mod5 = 3 Eszerint x ⊕ x-1 = 2 ⊕ 3 = 0, ami éppen az egységelem, tehát a mod5 összeadási műveletre nézve a 2 inverze a 3. A modm művelet tulajdonságaiból következik, hogy a művelet eredménye nem lehet nagyobb m-1-nél, tehát a zártság feltétele is biztosított. P 11 Példa: A negyedrendű csoport alatti modulo 4 összeadás művelettáblája: 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 A főátlóra szimmetrikus, tehát biztosan kommutatív művelet. Az Olvasó kisérelje meg felírni, hogy az adott esetben mi az alaphalmaz, igaz-e, hogy a struktúra Ábel csoport, igaz-e, hogy van olyan elem, amelyik sajátmaga inverze 22, és milyen –22 és +22 közé eső számok tartoznak a különböző cimkéjű maradékosztályokba. A modulo m összeadás tulajdonságaiból következő azonosságok Ha a ≡ b mod m, akkor 1. a ⊕ c ≡ b ⊕ c mod m 2. ac ≡ bc mod m Ha még c

≡ d mod m is fennáll, akkor 3. a ⊕ c ≡ b ⊕ d mod m 4. ac ≡ bd mod m 22 Esetenként kellemetlenséget okoz, ha egy csoportban van olyan szám, ami sajátmaga inverze. Ez egés zen biztosan elkerülhető, ha a csoport rendje prímszám. Erre később még visszatérünk Mutassa meg az Olvasó, hogy e „kellemetlenség” elkerülésére nem lenne elegendő azt kikötni, hogy a csoport rendje legyen 2, vagy bármely páratlan szám, viszont elegendő lenne azt kikötni, hogy a kardinalitás ne legyen négyzetszám. 21 D 8 definició: A modulo m szorzás A modulo m szorzás művelete nagyon hasonlít a modulo m összeadás műveletéhez. Egy a és egy b szám mod m szorzásakor az egyik lehetséges eljárás az, ha az a és a b számokat aritmetikai szorzással összeszorozva a c eredménynek képezzük a mod m maradékosztályát. Mivel az aritmetikai szorzás művelete disztributív az összeadás felett, írhatjuk a következőt: a = mx + r1; b = my + r2 ⇒ a.b = (mx +

r1)( my + r2) = m2xy + mxr2 + myr1 + r1r2 A jobboldal négy tagjából az első három egészen biztosan maradék nélkül osztható az m modulussal, tehát ha az eredménynek a modulo m maradékosztályára vagyunk kiváncsiak, akkor az a és a b tényezők összeszorzása helyett elegendő csak az r1 és r2 maradékosztályaik szorzatának mod m maradékosztályát kiszámítani. P 12 Példa: Végezzük el a=8 és b=7 mod 5 szorzását. 1. 8 x 7 = 56 és ennek mod 5 maradékosztálya 1, mert 56 = 11x5+1 2. 8 mod 5 = 3; 7 mod 5 = 2; 3 x 2 = 6 és 6 mod 5 = 1 P 13 Példa: Az Olvasó szerkesszen példát olyan esetre, amikor 1. Egy negatív és egy pozitív számot kell összeszorozni, tehát az eredmény negatív, (de a maradékosztálynak ekkor is pozitívnak kell lennie). 2. Két negatív számot szorzunk össze 3. Mindkét esetre érdemes olyan általános szabályt felírni az abszolut értékekkel, mint amilyent a negatív eredményt adó összeadásnál felírtunk. 4.

Alkalmazza az Olvasó a maradékok szorzásának elvét a mod m hatványozásra (Nagyon nagy hatványok esetén a maradék hatványa is okozhat túlcsordulást, hacsak le nem bontjuk az n-edik hatványra emelést n darab, ismételt mod m szorzásra. A modulo m összeadás és szorzás fentiekben mondott hasonlósága ellenére is van köztük nagyon lényeges különbség. A modulo m szorzás művelete tetszőleges m modulus esetén nem alkalmas arra, hogy az egészszámok halmaza felett véges csoportot alkosson. 22 P 14 Példa: Vizsgáljuk meg a következő hételemű halmazból és a modulo 8 egészszámú szorzásból (  ), mint multiplikatív műveletből álló algebrai struktúrát. A halmaz: A = {1, 2, 3, 4, 5, 6, 7,} A 2 is és a 4 is eleme ennek a halmaznak. Modulo 8 szorzatuk: 2  4 ≡ 0 mod 8 Mivel a 0 nem eleme a megadott halmaznak, ezért a művelet nem zárt az felett. Ezért a példa tot. 23 A halmaz A halmaza és a mod 8 szorzás, mint művelet nem alkot

csopor- Ha a 0 is a halmaz eleme lenne, akkor sem kapnánk csoportot, mert a 0-nak nincs multiplikatív inverze (mert nem lehet vele osztani). Ez meg azzal függ össze, hogy az adott példában nincs egységelem. P 15 Példa: Vizsgáljuk meg a következő hatelemű halmazból és a modulo 7 egészszámú szorzásból (  ), mint multiplikatív műveletből álló algebrai struktúrát. A halmaz: G = {1, 2, 3, 4, 5, 6,} A 2 is és a 4 is eleme ennek a halmaznak. Modulo 7 szorzatuk: 2  4 ≡ 1 mod 7 Az 1 pedig eleme a halmaznak. Persze ez még nem bizonyíték arra, hogy a mod 7 multiplikatív művelet valamennyi elempárra olyan eredményt ad, ami a eleme. 23 G halmaznak sőt, még félcsoportot sem, mert a műveletre vonatkozó legelemibb feltétel, azaz a zártság nem teljesül. A kétműveletes algebrai sztruktúrák között alapvető fontosságú az algebrai test, amely felett egy additív és egy multiplikatív műveletet definiálnak. (Ld később) Ott gondot okoz az,

hogy az additív művelet egységelemének (=0) az inverze a multiplikatív struktúrában nem értelmezhető. Ezért egy test esetén (mod p az ilyen) az additív zérustól eltekintenek, amikor inverzről van szó. Ilyen azonban a valós, a racionális stb számtest is. A 0-nak nincs inverze a multiplikatív struktúrában! Éppen azért mert a testek is kellenek ettől az additív nullától (jobban modva az additív zéruselemtől) eltekintenek. 23 Mivel nincs túl sok elem, ezért könnyen megszerkeszthetjük az adott feletti mod 7 (  ) multiplikatív művelet tábláját: G halmaz  1 2 3 4 5 6 1 1 2 3 4 5 6 2 2 4 6 1 3 5 3 3 6 2 5 1 4 4 4 1 5 2 6 3 5 5 3 1 6 4 2 6 6 5 4 3 2 1 A művelettáblából látható, hogy a mod 7 szorzási művelet eredménye mindíg a G halmazban meglévő elem. Ezért a művelet most zárt, tehát csoportról beszélhetünk A művelettábla a főátlójára szimmetrikus, tehát a művelet kommutatív is. 24 Az adott esetben

létezik a multiplikatív mod 7 művelethez tartozó egységelem (itt éppen 1) és minden halmazbeli elemnek van multiplikatív inverze is, amelyekre igaz, hogy ∀ a, a-1 ∈ G ⇒ a  a-1 ≡ 1 mod 7 Ez pedig mindíg teljesül, ha a modulus prímszám. Figyelemre méltó, hogy az aritmetikai szorzás invertálásához szükség van a racionális törtekre. A mod m szorzás ezzel szemben olyan halmaz felett is értelmezhető, amely kizárólag csak az egészszámokat tartalmazza. T 3 tétel a multiplikatív csoportokra A p-1 rendű S = {1, 2, 3, . ,p-1} halmaz és a felette értelmezett modulo p multiplikatív művelet kommutatív (azaz Ábel) csoportot alkotnak, de kizárólag csak akkor, ha p prímszám. A bizonyítást –jóllehet nem bonyolultitt nem közöljük. D 9 definició: Egy csoport elemeinek a rendje. Legyen g a G csoport egy eleme és értelmezzük a csoport felett a „.” szorzási műveletet és a megszokás okán értelmezzük g hatványait a

következőképp: g2 = g.g; g3 = g.gg . 24 A kommutatív csoport pedig Ábel csoport. 24 Jelölje ord( g ) a csoport g elemének a rendjét. 25 ord( g ) az a legkisebb pozitív egészszám, amelyre igaz, hogy gord(g) = a csoport egységeleme Ha az egységelemre a korábban már használt általános e jelölést alkalmazzuk, akkor gord(g) = e mod m Ha a mod m-et nem írtuk volna elő, akkor az összefüggés első részéből ord(g) = logg e lehetne, de teljesülnie kellene még annak is, hogy legyen ez a lehetséges pozitív egészek közül a legkisebb. Az ilyen logaritmust diszkrét logaritmusnak nevezzük és (sokkal) később, majd az aszimmetrikus kriptorendszerek kapcsán hivatkozunk ilyen, vagy hasonló diszkrét logaritmusokkal operáló rendszerekre. 26 P 16 Példa: Vizsgáljuk meg a P 15. példában már tárgyalt hatelemű halmazból és a modulo 7 egészszámú szorzásból (  ), mint multiplikatív műveletből álló algebrai struktúrában a G halmaz

elemeinek a rendjét. A halmaz: G = {1, 2, 3, 4, 5, 6,} ; A csoport egységeleme a multiplikatív mod 7 (  ) műveletre 1. (Ezt a P 15 példa kapcsán már beláttuk és jegyezzük meg jól, mert alább többször is alkalmazzuk!) Az 1 elem rendje ord (1). Erre igaznak kell lennie, hogy 1ord(1) = 1 mod 7 Nos, ezt az egyenletet kielégíti mind a 0 kitevő, mind az 1 kitevő 27. A D9 definició szerint azonban az elem rendje „.az a legkisebb pozitív egészszám” Eszerint az elem rendje nem lehet 0, csakis 1. 28 Tehát ord(1) = 1 Vizsgáljuk meg külön-külön a csoport további elemeit! 25 Az angol terminológia az „order” szót használja az itt (is) használt magyar „rend” szóra. Ebből származtatja egy g elem rendjére az ord( g ) jelölést, amit mi is alkalmazunk. 26 A diszkrét logaritmusokat nem lehet sorozatokkal kiszámítani, hanem (nagyrészt) próbálgatással kell megkeresni, ami nagy számok esetén igen hosszadalmas folyamat. Az aszimmetrikus

kriptográfiában pontosan olyan függvényekre „vadásztak” a gyakorlati módszerek ifejlesztői, amelyek egyik irányban aránylag könnyen kiszámíthatók, de az inverzük kiszámítása nagyon hosszadalmas. Nos, a diszkrét logaritmusok pontosan ilyenek 27 És egyáltalában bármilyen egész kitevő, mert 1-nek bármelyik egész hatványa 1 (sőt a tört hatványai is, de itt a legkisebb pozitív egészszámot kell megkeresni. 28 A mod 7 multiplikatív művelet itt azért nem „zavar”, mert 1-nek a mod7 maradéka is 1. 25 A 2 elem rendjét egy kissé bonyolultabb meghatározni. A definicióból következően kell, hogy 2ord(2) = 1 mod 7 legyen. Keressünk tehát olyan hatványkitevőt, amely kitevőre emelve 2-t olyan számot kapunk, amelynek mod 7 maradéka 1. Ilyen egészszám a 3, mert 23 = 8 és 8 ≡ 1 mod 7; Tehát ord(2) = 3 Hasonlóképp szükséges, hogy 3ord(3) = 1 mod 7 legyen. Keressünk tehát olyan hatványkitevőt, amely hatványra emelve 3-at olyan

számot kapunk, amelynek mod 7 maradéka 1. Ilyen egészszám a 6, mert 36 = 729 és 729 ≡ 1 mod 7, (729 -ben pontosan 104-szer van meg a 7 és marad 1 Ráadásul nincsen 6-nál kisebb ilyen pozitív egészszám.) Tehát ord(3) = 6 A csoport többi elemének a rendje a következő: 4ord(4) = 1 mod 7 és ord(4) = 3 mert 43 = 48 és 48 ≡ 1 mod 7 5ord(5) = 1 mod 7 és ord(5) = 6 mert 56 = 15625 és 15625 ≡ 1 mod 7 6ord(6) = 1 mod 7 és ord(6) = 2 mert 62 = 36 és 36 ≡ 1 mod 7 Nem kell, hogy a csoport valamennyi tagjának különböző legyen a rendje de (itt) a mod7 multiplikatív műveletből következik, hogy bármelyik elem rendje csakis 1 és 6 közé eshet. (az intervallum határait is beleértve) Általánosságban tehát egy G csoport a ∈ G elemenek rendje: 1 ≤ ord(a) ≤ (m-1) 26 D 10 definició: Az alcsoport. Jelölje S a G csoportnak egy alcsoportját. Ha ∀ a, b ∈ S–re igaz, hogy c = a  b- 1 és c ∈ S akkor S alcsoportja G -nek. S akkor alcsoportja

G–nek, ha a  multiplikatív csoportműveletre nézve zárt (mármint S ) éstartalmazza a szükséges inverzeket. Minden más csoport tulajdonságot is örököl G –től. Ez, persze, azt jelenti, hogy S Ez más szóval azt jelenti, hogy saját maga is csoport. A halmazok és részhalmazok viszonyából is mert és értelemszerüen alkalmazott megnevezés szerint S valódi alcsoportja G–nek, ha S ⊂ G és S ≠ G. P 17 Példa: A modulo 9 összeadási művelet alatti egészszámok csoportjának valódi alcsoportjai a mod 9 művelet alatti {0,} és a {0, 3, 6} alcsoportok. A modulo 16 összeadási művelet alatti egészszámok csoportjának valódi alcsoportjai a {0}, a {0, 4, 8, 12}, és a {0, 2, 4, 6, 8, 10, 12, 14} alcsoportok. Érdemes felfigyelni arra, hogy a felsorolt példákban minden alcsoport tartalmazza az additív művelet egységelemét (azaz a 0-át). Kell is, hogy így legyen, mert mint az inverz elem fogalmának bevezetésekor (Ld. az 6 oldalon), majd a

csoport FD 3 definiciójánál láttuk az egységelem és az inverz elempárok kölcsönösen feltételezik egymás exisztenciáját. Mivel az additív csoportművelet egységeleme a 0, ezért mindegyik alcsoportnak is tartalmaznia kell Az inverzek létezése nélkül ugyanis nem teljesítené a csoportra előírt feltételeket D 11 definició: Bal- és jobboldali mellékosztályok. Legyen S alcsoportja G-nek a ⊛ művelet alatt. S-nek G-beli baloldali mellékosztálya G-nek egy olyan részhalmaza, amelynek elemei x ⊛ S alakúak azaz az itt említett részhalmaz a következő: {x ⊛ s | s ∈ S} Hasonlóan S-nek G-beli jobboldali mellékosztálya G-nek egy olyan részhalmaza, amelynek elemei S ⊛ x alakúak azaz az itt említett részhalmaz a következő: { s ⊛ x | s ∈ S } Ha a ⊛ művelet kommutatív, akkor a bal- és a jobboldali mellékosztályok azonosak. A továbbiakban az ilyen esetekben egyszerüen csak mellékosztályról szólunk. 27 Az eddig tárgyalt

additív és multiplikatív modulo m műveleteknél két egészszámot kongruensnek (más szóval ekvivalensnek) neveztünk akkor, ha az m modulussal, mint osztóval maradékos osztást végrehajtva rajtuk azonos maradékokat kaptunk. Felírva e két, egymással kongruens szám már korábban bevezetett maradékos alakjait: a = x.m + r; és b = ym + r ⇒ a ≡ b mod m azaz az a és b egészszámok csak az x és y szorzókban különböznbek (de ezekkel a szorzókkal nem számoltunk, mert a lényeg az m modulus és az r maradék volt). Az a és a b számok különböznek akkor is, ha más-más modulussal adják ugyanazt a maradékot, azaz a = x.m1 + r; és b = xm2 + r; de m1 ≠ m2 ⇒ a ≠ b A mellékosztályok bevezetésével ezt a koncepciót tovább általánosítottuk úgy, hogy megengedtük, hogy a modulusok alcsoportok legyenek. Az itt felírt aritmetikai ⊛ csoportműveletet alkalmazhatunk, a S alcsoportját. Ekkor az x ⊛ S művelet szorzás helyett az

általánosításkor bármilyen modulus helyett pedig G-nek egy eredménye sem egy csoport-elem, hanem egy alcsoport lesz. Az eddigiekben tárgyalt additív és multiplikatív modulo m műveletek kommutatívak is voltak, bár a kommutativitás a csoportműveletekre nézve nem előírás. Ezért egy nem kommutatív ⊛ csoportművelet esetén a ⊛ b ≠ b ⊛ a és emiatt kell a jobb és a baloldali operandusokat megkülönböztetni. Ez az oka annak is, hogy itt, a mellékosztályok definiciójakor bal- és jobboldali mellékosztályokról beszélünk. P 18 Példa: A P 17 példában láttuk, hogy a modulo 9 összeadási művelet alatti egészszámok csoportjának egyik valódi alcsoportja a mod 9 művelet alatti S = {0, 3, 6} alcsoport. Képezzük ennek egy mellékosztályát úgy, hogy az alcsoport elemeihez rendre mod 9 hozzáadunk 1-et: Tehát minden s ∈ S–hez 1-et hozzáadva S1 = {1, 4, 7} Képezzünk most egy másik mellékosztályt! Tehát minden s ∈ S–hez 2-t

hozzáadva S2 = {2, 5, 8} Ha 3-at adnánk hozzá (mod 9) az S = {0, 3, 6} alcsoport minden eleméhez, akkor az S = {3, 6, 0} alcsoportot, vagyis saját magát kapnánk vissza. S–nek két mellékosztálya van (S1 és S2) és ezek mind egymáshoz képest, mind S–hez képest diszjunkt alcsoportok. Az adott példában tehát 28 D 12 definició: Az indukált mellékosztály-partició. Egy G- csoport különbözőS alcsoportjának mellékosztályai diszjunkt halmazok. A bizonyítástól itt is eltekintünk. A P 18 példa mindenesetre azt mutatja, hogy az S halmaz mellékosztályainak nincsenek azonos elemei és ez be is látható abból, hogy hogyan képeztük a mellékosztályokat. (Az itt nem közölt bizonyítás is lényegében ezt mutatja meg.) G csoport S alcsoportjának mellékosztályai G-t különböző és diszjunk részhalmazokra particionálják 29 G-nek ezt a diszjunkt részhalmazokra való felosztását G- nek az S halmaz által indukált mellékosztály

particiójá- Ez a tétel arra utal, hogy egy nak nevezik. T 4 tétel: Lagrange tétele a mellékosztályok rendjére. Ha S alcsoportja G-nek akkor ord(S) | ord(G) azaz ord(S) valódi, maradék nélküli osztója ord(G)-nek 29 A particionálás jellemzően összefügg az ekvivalencia relációval. Ha a,b,c ∈S és a= b akkor Snek egy S’ ré szhalmazába ( itt: m ellékosztályába) t artoznak, d e h a c ≠a, a kkor az S-nek eg y másik S” részhalmazába tartozik, amelynek nincs egyetlen közös eleme sem S’-vel. Imígyen az S halmaz elemei közötti ekvivalencia reláció az S halmazt diszjunkt részhalmazokra particionálja. 29 3 Kétműveletes algebrai struktúrák. Az algebrai struktúrák „családfája” ( Ld. a 12 oldalon) kapcsán megmutattuk, hogy léteznek kétműveletes struktúrák is, de mindeddig a „családfának” csak az egyműveletes struktúrák alatti ágát vizsgáltuk. A következőkben a kétműveletes struktúrákkal foglalkozunk,

nevezetesen a gyűrűkkel és a testekkel. végül pedig egy többműveletes, komplex algebrai struktúrával, a vektorterekkel. A származtatásuk lényegében ugyanúgy történik, mint az egyműveletes struktúrák esetében, de itt (ti. a kétműveletes struktúráknál) mindkét műveletre, valamint ezek egymáshoz képesti viszonyára is teszünk megkötéseket a „családfa” kialakítása során. A két- és többműveletes algebrai struktúrák családfájának három fő ágát definiáljuk és ezeket külön-külön mutatjuk be a következőkben. Az így leszármaztatott „családfa” egyes fő ágai tehát a következők: 1. A gyűrű (Ring) 2. A test (Field) 3. A vektorterek (Vector Spaces) Ezt szemlélteti a következő oldal ábrája (egyelőre a műveletekre vonatkozó részletes megkötések nélkül.) 30 Az egyetlen kikötés a zártság Mûvelet Az egyetlen kikötés a zártság Mûvelet Zárt mûvelet Nem üres Kétmûveletes algebrai struktúra

Halmaz (+) Mûvelet Vektorok összeadása Min. másod rendû T Halmaz Test (F) Gyûrû (R) . Vektortér ( ) Vektorok skalárral való szorzása Az additív mûvelet kommutatív és egységelemes. A multiplikatív mûvelet asszociatív és disztributív az additív mûvelet felett Az additív mûvelet kommutatív, asszociatív és invertálható. A multiplikatív mûvelet asszociatív és disztributív az additív mûvelet felett A multiplikatív mûvelet ráadásul még invertálható is T - {0 felett} V Halmaz Vektor halmaz Két mûveletet"megörököl" a testtõl és további mûveletei vannak a V halmaz felett Komplex, több-mûveletes és több halmaz felett értelmezett struktúra NB:A test és a vektorterek esetében nem csak a mûveletekre, hanem a T (és V) halmaz(ok)ra is teszünk kikötéseket . 31 D 13 definició: A gyűrű Az R 30 gyűrű kétműveletes algebrai struktúra, amely 1. Kommutatív csoportot alkot az additív ( ⊕ )

műveletre nézve 2. A multiplikatív (⊙) művelet asszociatív, azaz (a 3. A ⊙ b) ⊙ ⊙ c = a ⊙ ( b ⊙ c) minden a,b,c ∈ R-re művelet disztributív a ⊕ művelet felett Fontos, hogy a gyűrű minden további alfajánál változatlan az additív struktúrára előírt kommutativitás és az, hogy az additív műveletnek egységeleme van. Nem is „hozunk be” az additív művelettel kapcsolatos semmilyen további feltételt. A gyűrűből „származtatott kommutatív gyűrű, egységelemes gyűrű és az egységelemes kommutatív gyűrű csakis a multiplikatív műveletre előírt, további követelményekben különböznek, mint azt a következő ábrán látható „családfájuk „ is mutatja. 30 Az „R” jelölés a gyűrű angol nevéből (= Ring) származik 32 Az egyetlen kikötés a zártság Nem üres . Mûvelet Mûvelet Kommutatív mûvelet Az egységeleme "0" Asszociatív mûvelet, amely disztributív a (additív) mûvelet felett

Gyûrû (R) Halmaz A . (multiplikatív) mûveletnek is van egységeleme A (multiplikatív) mûvelet is kommutatív Egységelemes gyûrû Mindkét (tehát mind az additív, mind a multiplikatív) mûveletnek van egységeleme és mindkettõ kommutatív Az egyetlen kikötés . a zártság Kommutatív gyûrû Egységelemes kommutatív gyûrû 33 A gyűrű és speciális alfajai. Természetesen mindkét műveletre alapfeltétel a zártság. Figyeljük meg, hogy valamennyi „gyűrű tipusú” struktúrában igaz, hogy az additív művelet kommutatív és ennek a műveletnek van egységeleme, amit 0-val jelölünk. A kommutativitása miatt, persze, asszociatív is. A multiplikatív műveletre –első közelítésben- csak az van előírva, hogy asszociatív legyen. Az additív művelet kommutativitása miatt a gyűrű az additív műveletrére nézve Ábel csoport, de –általános esetben- a multiplikatív műveletére nézve nem az. A multiplikatív műveletre –első

közelítésben-- nincs kikötve, hogy legyen egységeleme. Ha kikötjük azt is, hogy a multiplikatív műveletnek is legyen egységeleme (ne csak az additív műveletnek) akkor egységelemes kommutatív gyűrűről beszélünk. Az additív művelet (0-val jelölt) egységeleme természetesen nem azonos a multiplikatív művelet (egyébként 1-gyel jelölt) egységelemével. Ebből aztán a 0; 1 jelölések miatt gondok is származhatnak. nevezetesen az, hogy az additív művelet „0” egységeleme a multiplikatív művelet zéruseleme (lehet) s emiatt a multiplikatív műveletnek –úgy tünhet- zérus osztója lehet. Mindenesetre a multiplikatív műveletnek nincs a zérus elemre vonatkoztatott inverze Emlékezzünk arra, hogy ahhoz, hogy egy algebrai struktúrában minden elemnek van inverz eleme is (egy műveletre nézve) az azt jelenti, hogy az a művelet invertálható. A gyűrű „családfájára” hivatkozva ez másképp is megfogalmazható: Amíg a „családfa a

gyökerétől indulva mind újabb és újabb ágakra bomlik, semmi akadálya annak, hogy ezeket az elágaztatásokat mind újabb s újabb feltételeket vagy (az egyik v. másik műveletre vonatkozó) kikötések bevezetésével állítsuk elő Ha azonban valahányadik lépésben két ágat egyesítünk (amint azt a kommutatív, egységelemes gyűrű esetében tettük) akkor könnyen lehet, hogy valamilyen ellentmondás keletkezik a korábban már bevezetett feltételek között. Itt történetesen az, hogy az additív művelet invertálásához szükség van a 0 ∈ elemre,de a multiplikatív művelet csak az A – {0} felett lehet invertálható. 32 A Az azonos hatványkitevőjű tagok egybites, bináris együtthatói mod 2 adhatók és adandók össze. A polinomok szorzásakor a tagok kitevőit kell mod k összeadni, ahol a k-szám meg van adva. Ezt a modellt alkalmazzák pl a ciklikus Hamming kódok 34 P 19 Példák: A csupa egész elemet tartalmazó k-ad rangú négyzetes

mátrixok egységelemes kommutatív gyűrűt alkotnak a „szabványos” mátrix összeadásra és szorzásra, mint csoportműveletekre nézve. Az egységelem a k-ad rangú egységmátrix lesz, amelynek a főátlójában csupa 1-es elem van (azaz k-ad rangú egységmátrixnál k darab) és a mátrix minden más eleme 0. Az egészszámok feletti modulo m összeadás és a modulo m szorzás egységelemes kommutatív gyűrűt alkotnak. Valamennyi polinom, amelyek koefficiensei egybites bináris számok egységelemes kommutatív gyűrűt alkot a szabványos polinom-összeadás és szorzás, mint csoportműveletek alatt. 32 Ezt a gyűrűt rendszerint F2[x]-szel, vagy GF(2)[x]-szel jelölik. A gyűrűk és a polinomok nagyon fontosak az algebrai kódok elméletében. Közülük is különösen fontosak lesznek azok a polinomok, amelyek koefficiensei un. véges testekből származnak. (Ld a „test” fogalmát a következő pontban) A test és speciális alfajai. D 14 definició: A test Az

F 33 test kétműveletes algebrai struktúra, amely 1. Kommutatív csoportot alkot az additív ( ⊕ ) műveletre nézve A ( ⊕ ) művelet egységelemét 0-val jelöljük. 2. Ha az F testből eltávolítjuk az additív művelet egységelemét, azaz 0-át, akkor a multiplikatív (⊙) műveletre nézve kommutatív csoportot alkot, amelynek egységeleme az 1. 3. A a ⊙ művelet disztributív a ⊕ művelet felett, azaz ⊙ (b ⊕ c) = (a ⊙ b) ⊕ ( a ⊙ c) minden a,b,c ∈ R-re Minden testnek kettős csoport-jellege van: A test összes eleme additív, egységelemes kommutatív csoportot alkot, a nemzérus elemei pedig egy egységelemes multiplikatív csoportot. Ez a megközelítés hasznos lesz a véges testek alkotásakor. 32 Az azonos hatványkitevőjű tagok egybites, bináris együtthatói mod 2 adhatók és adandók össze. A polinomok szorzásakor a tagok kitevőit kell mod k összeadni, ahol a k-szám meg van adva. Ezt a modellt alkalmazzák pl a ciklikus Hamming

kódok 33 Az algebrai test neve az angolban „field”. Ennek az eső betüje után szokás az algebrai testre az „F” jelölést alkalmazni, amit mi is használunk itt és a továbbiakban 35 A véges rendű (kardinalitású) testeknek különösen fontos szerepük van a kódoláselméletben. Résztest az F test olyan részhalmaza, amelyre érvényes a test definciójának valamennyi kritériuma Prímtest az olyan test, amelynek nincs valódi (azaz saját magától különböző) részteste P 20 Példák végtelen testekre: 1. A racionális számok a „legkisebb” 34 végtelen test 2. A valós számtest 3. A komplex számtest 4. A mod p (p=prímszám) maradékosztályok teste 5. Az egészszámok feletti szorzásnak nincs multiplikatív inverze, ezért az egészszámok nem alkotnak testet D 15 definició: A q-ad rendű Galois test: GF(q) A véges testek fogalmát Evariste Galois alkotta meg és ezért a véges testeket róla nevezték el Galois 35 testeknek A legegyszerűbb

Galois test a GF(2) Ezt legtöbbször a T = {0,1} bináris halmaz felett értelmezik. Alapértelmezésben a ⊕ művelet a kizáró VAGY (=XOR) művelet, amelynek művelettáblája a következő: ⊕ 0 1 0 0 1 1 1 0 Ez a művelet a T = {0,1} halmaz felett értelmezett és erre a halmazra nézve zárt is, továbbá a művelettábla a főátlójára szimmetrikus, tehát a művelet kommutatív is. Létezik a művelet egységeleme is: a 0, mert a ⊕ 0 = a ∀ a ∈ T 34 Nos igen, a végtelen fogalomkörben is értelmezhető a kisebb és a nygobb számosság fogalma. Megszámlálhatóan v égtelen a t ermészetes és r acionális s zámok hal maza és en nek a kardinalitása a „legkisebb” végtelen szám. 35 Ejtsd: Galoá 36 Minden a ∈ T –re létezik az inverz elem, azaz a-1 ∈ T is egyszerüen úgy, hogy 0nak 1 az inverze 1-nek pedig 0 mert 1 művelet zárt. ⊕0=0⊕1= Összefoglalva: A T = {0,1} bináris halmaz felett a inverze is. ⊕ 1 és a, a-1 = 0, 1∈ T

tehát a művelet zárt és létezik az Más a helyzet azonban a multiplikatív művelettel. A ⊙ multiplikatív műveletet művelettáblája a következő: ⊙ 0 1 0 0 0 1 0 1 Elvileg két lehetőségünk van: 1. Ha a T = {0,1} halmaz felett értelmezzük ezt a műveletet, akkor ugyan zárt, és elvileg 0-nak inverze lehetne 1 (és viszont) de nem igaz, hogy a ⊙ a-1 = 1, azaz a művelet nem invertálható. 36 Tehát zárt, de nem invertálható 2. A másik lehetőség az, hogy „csak” a T – {0} = {1} halmaz felett értelmezzük a ⊙ műveletet, de ekkor meg nem zárt, mert az eredménye –a művelettábla szerint-- 0 is lehet, ami kimutat a T = {1} halmazból. Ekkor tehát létezik az inverz (ti. 1-nek 1 az inverze), de nem teljesül a zártság A feloldás az, hogy szorzásra nézve az additív zéruselem inverzének létezésétől eltekintenek. Ezzel rövidre zárják a problémákat 36 Ahhoz, hogy invertálható legyen egészen másként kellene definiálni a

művelettáblát. Pl úgy, hogy 0 ⊙ 0 = 1 legyen. (Mellesleg ezt szokás ekvivalencia műveletnek –és nem relációnaknevezni) 37 A prímszám elemű Galois testek A modulo m aritmetikai műveletekre vonatkozó T1 és T2 tételek kielégítése esetén p prímszám rendű Galois testeket lehet alkotni. Vizsgáljuk pl. a {0, 1, 2, ,p-1} egészszámok p rendű halmazát A modulo p összeadás alatt ezek az elemek egy additív, kommutatív (és a 0 miatt egységelemes) csoportot alkotnak. Az előbbi halmaz {1, 2, . ,p-1) egészszámok p-1 rendű valódi részhalmaza felett értelmezett modulo p szorzással pedig egy multiplikatív, kommutatív (és az 1 miatt egységelemes) csoportot alkotnak. Ha megengedjük, hogy ez a két művelet egymás felett disztributív legyen, akkor mindez együtt egy testet alkot. T 5 tétel a prímrendű Galois testekre A {0, 1, 2, . ,p-1} egészszámok (ahol p=prímszám) GF(p) Galois testet alkotnak a modulo p összeadás és a modulo p szorzás

alatt. P 21 Példa: Szerkesszünk GF(3)-at. Használjuk a {0, 1, 2,} egészszámok halmazát a mod 3 összeadás és szorzás alatt. A disztributivitást az biztosítja, hogy 0 ⊙ a= 0 minden a ∈ GF(3)-ra. Az additív művelet táblája a következő: ⊕ 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 Lévén a főátlóra szimmetrikus, a művelet kommutatív. Van egységeleme (=0) és ezért minden elemnek létezik az inverze is úgy, hogy a⊕a-1 =0 minden a ∈ GF(3)-ra. Pl 2 (A 0 saját maga inverze.) ⊕ 1 = 0, tehát 2-nek 1 az inverze és viszont. 38 A multiplikatív művelet táblája ⊙ 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1 A művelettábla megint csak szimmetrikus a főátlójára, tehát a művelet kommutatív. Egységelem az 1 37, de a 0 miatt az adott halmazon belül sincs mindegyik elemnek inverze csak, ha a 0-át kizárjuk. T 6 tétel: Prímhatvány rendű Galois testek Bizonyítható, hogy nem akármilyen q=egészszámra létezik véges GF(q). Bizonyítható továbbá, hogy

minden pm elemű halmazra létezik GF(pm) ahol p tetszőleges prímszám és m tetszőleges egészszám (továbbá mind p, mind m pozitív számok). Csakis olyan q-ad rendű véges GF(q) Galois testek léteznek, amelyek esetében q egy pozitív p prímszám nem negatív egész hatványa. Alább, a vektorterek kapcsán tárgyaljuk majd, hogy pm rendű véges testeket némileg bonyolultabb műveletekkel hozunk majd kapcsolatba, mint az eddig tárgyalt modulo q aritmetikák voltak. Látni fogjuk, hogy a q = pm rendű véges testeket a GF(p) test felett fogjuk generálni. 37 különben nem lehetne csoport 39 4 Vektorterek. Az algebrai struktúrák „családfája” ( Ld. a 12 oldalon) kapcsán elmondtuk, hogy egyés többműveletes struktúrákat különböztetünk meg de eddig csak az egy alaphalmazra épülő egy- és kétműveletes struktúrákkal foglalkoztunk Itt most egy az előbbieknél minden szempontból komplexebb struktúráról, nevezetesen a vektorterekről lesz szó.

Legyen V az elemek egy olyan halmaza, amelyeket vektoroknak nevezünk és egy algebrai test, amelynek elemeit skalároknak nevezünk. F F test elemei között már a test definiciójából következően (művelettábláikkal) definiálva van két 38 művelet, de itt és most bevezetünk a V és az F test feletti Az további két műveletet. 39 38 Mindkettőt „megörökli” a skalár testtől a vektortér, de a multiplikatív műveletet úgy, hogy az a skalárok hal mazának e gy ai eleme és a v ektorok hal mazának egy vj eleme k özött l esz értelmezve. Ezért állítjuk itt, hogy további két műveletet vezetünk be, holott egyelőre „csak” 3 művelet van értelmezve. 39 Pontosabban c sak m ajd j óval al ább a 51. oldalon vezetjük be a negyedik műveletet ezen az összetett struktúrán. 40 Vektorok összeadása: Legyen mind v1 mind v2 V –nek egy-egy eleme azaz vektorok, amelyekre v1 , v2 ∈ V Értelmezzük ezek között a „+” jellel jelölt

vektor-összeadást, amelyre vi + vj = vk ∀ vi , vj , vk ∈ V Ez a művelet a V halmaznak önmagával alkotott direkt szorzatát 40 leképezi magára a V halmazra, azaz V x V ⇒ V Vezessük be továbbá az F testből vett α ∈ F skalárok és a V halmazból vett v ∈ V vektorok „.”-tal jelölt szorzását 41 w = α . v; v, w ∈ V; 40 α ∈F Direkt, vagy Descartes (olv: Dékárt) szorzat: A V halmazból vett rendezett elempárok összes kombinációját k épezi és alkalmazza r á i tt épp en a v ektorok ös szeadásaként bev ezetett műveletet. Ha minden ilyen összeadás eredménye szintén eleme V-nek, akkor az adott direkt szorzatot V-re, azaz saját magára képezi le ez a művelet. 41 Nem vektorszorzat é s nem skalárszorzat, h anem e gy F-beli s kalár és egy V-beli v ektor összeszorzása, am elynek er edménye egy v ektort a d. S zemléletesen: ny újtja/zsugorítja, v agy tükrözi a v vektort. 41 D 16 definició: Az F test feletti V vektortér

Akkor, és csakis akkor nevezzük következő feltételek V-t az F feletti vektortérnek, ha teljesülnek a 1. A V kommutatív csoportot alkot a + vektor-összeadási művelet alatt 2. Bármely skalár λ ∈ F –re és v ∈ V-vektorra teljesül, hogy λ v = u ∈ V Eszerint tehát a skalárral való szorzás „.” művelete és (az alábbiak szerint) a vektorok-összeadásának „+” művelete kölcsönösen disztributívak egymás felett, azaz α . (u + v) = α u + α v 42 β ∈ F –re és minden v ∈ V -re (α . β ) v = α (β v) 3. Asszociativitás: minden α, 4. A multiplikatív egységelem: az F –beli 1 Ez egy v vektornak skalárral való szorzásakor is egységelemként működik, azaz ∀ v∈V ⇒ 1 . v = v F –et a V vektortér skalár testjének vagy, más néven, alaptestjének nevezik. 42 A ⊕ művelet az F test additív művelete, a „ + „ művelet pe dig a V vektorhalmaz f eletti additív művelet, amellyel az utóbbi az 1. feltétel

szerint kommutatív csoportot alkot Ezt a két additív műveletet tehát nem szabad egymással összetéveszteni! 42 A már korábban is alkalmazott „családfa” ábrázolással a vektortér, mint összetett algebrai struktúra a következő ábrával szemléltathető: Zárt, additív mûvelet (1) Zárt, multiplikatív mûvelet Zárt, additív mûvelet (2) . + Skalárok modulo m összeadása Vektorok komponensen -kénti összeadása . Min. Skalár máhalmaz sod rendû A csoportkódok algebrai modelljeinél kételemû {0,1} halmaz, s ekkor az F test GF(2), az (1) additív mûvelet pedig mod 2 összeadás (Alap) test (F) . Vektortér VekV tor Halmaz halmaz Vektorok A vektorkomponensen algebrából -kénti ismert szorzása az F skalárszorzat testbõl amit itt vett belsõ skalárokkal szorzatnak (nyújtás, nevezünk tükrözés) Zárt, multiplikatív mûvelet * A vektorterek általános tárgyalásakor nem kel kikötni, és nem is kötik ki, hogy az F

skalár-test a GF(2) legyen. Az alábbi fogalmi definicióknál mi sem kötjük ki ezt A szám n-es 43 Legyenek a v0; v1; ,. ; vn-1 skalárok, valamint az u0; u1; , ; un-1 skalárok az F skalártest elemei. Ekkor az ezekből alkotott szám n-esek egyfajta vektorokat határoznak meg a következőképp: v = ‹v0; v1; ,. ; vn-1› u = ‹u0; u1; ,. ; un-1› Itt és a következőkben is a vektorokat a nyomtatásban szokásos módon, azaz kövér (bold) betütipussal jelöljük, a skalárokat meg nem, de ha szükség van a kiemelésükre, akkor dőlt (Italics) betütipussal. 43 Az angol terminológiában: n-tuple. 43 A skalár-halmazban ill. a skalártestben természetesen nem értelmezhető a fenti szám n-esek egyes tagjainak a sorrendje, de a bevezetett v és u vektoroknál már igenis számít, hogy a szám n-esben melyik komponensnek mi a helye. Úgy kell ezt érteni, hogy a szám n-esek általános, pl. ‹v0; v1; ,. ; vn-1› alakjában a v0; v1; ,. ; vn-1 skalár elemeket

változóknak tekintjük, amelyek az F alaptest skalár értéket vehetik fel. Ha történetesen az F alaptest a GF(2) Galois test, akkor mindegyik vi változó csakis a 0 vagy az 1 értéket veheti fel. A vektorok bemutatott, azaz skalár komponenseikkel (= szám n-essel) való ábrázolása nagyon kényelmes módot ad mind a vektorok összegezésére, mind a skalárral való szorzásukra. Legyen α ∈F ∧ {vi} ⊆ F ⋀ {ui} ⊆ F akkor az u és a v vektorok összeadása : u + v = ‹v0⊕ u0; v1⊕ u1;. ; vn-1⊕ un-1;› a v vektor szorzása az α skalárral pedig: α v = ‹α v0; α v1; ,. ; α vn-1› P 22. Példa (Vektorterek GF(2) felett): Legyen a skalár-test a GF(2), azaz F = {0,1} és szerkesszünk ennek az elemeiből szám n-eseket. Ez úgy is felfogható, hogy ezek a szám n-esek n bites bináris kódszavak, vagy n komponensű vektorok Ezek a szám n-esek egy Vn vektorteret alkotnak, amely vektortérnek összesen 2n különböző eleme lehet, mert az n bites

bináris kódszavakból összesen 2n darab van. A Vn vektortér kardinalitása tehát ebben az esetben 2n. Ha pl. az ötbites bináris kódszavakat vizsgáljuk, azaz n = 5, akkor ezekből összesen 25 =32 van, tehát a V5 vektortér kardinalitása 32. P 23. Példa A valós számokból alkotott n X n –es négyzetes mátrixok végtelen kardinalitású vektorteret alkotnak a valós számokból álló számtest felett. 44 A lineáris kombinációk A vektorterek felett definiált eddigi műveletek segítségével kiszámíthatók a vektortér vektorainak lineáris kombinációi. Vn Legyenek a v1; v2; ,. ; vn vektorok mind elemei a V vektortérnek és legyenek az α1; α2; ,. ; αn skalárok elemei az F testnek. Mivel V egy kommutatív csoport a + művelet alatt, a v = α1 v1+ α2 v2+ α3 v3+ . + αn vn szintén V –beli vektor lesz. A lineáris kombinációk fogalma már csak azért is fontos, mert egy vektorteret éppen arról lehet felismerni, hogy valamennyi eleme

előállítható néhány speciálisan kiválasztott vektora lineáris kombinációjaként. (Erről alább még bőven szólunk majd) P 24. Példa: Lineáris kombinációk Legyenek az α1; α2; α3 skalárok a GF(2) beli, tehát csakis két értéket felvehető elemek és a V3 vektortér vektorai közül legyenek adottak a következők: v1 = 1 0 0 0 1 v2 = 1 1 1 0 0 v3 = 1 0 0 1 1 Képezzük e vektorok összes lineáris kombinációját! α1, α2, α3 α1 v1+ α2 v2+ α3 v3 = 0,0,0 0v1+ 0v2+ 0v3 = 0 00000 0,0,1 0v1+ 0v2+ 1v3 = v3 10011 0,1,0 0v1+ 1v2+ 0v3 = v2 10001 0,1,1 0v1+ 1v2+ 1v3 = v2+ v3 01111 1,0,0 1v1+ 0v2+ 0v3 = v1 10001 1,0,1 1v1+ 0v2+ 1v3 = v1+ v3 00010 1,1,0 1v1+ 1v2+ 0v3 = v1+ v2 01101 1,1,1 1v1+ 1v2+ 1v3 = v1+ v2+ v3 11110 45 Látható, hogy • Három bináris skalárról lévén szó összesen 23 =8 lineáris kombináció létezik. • Éppen ezért az adott példa vektorterének összesen 8 vektora van. • A

vektortér valamennyi vektorát képezni tudtuk három, un. lineárisan független vektor lineáris kombinációinak kiszámolásával. (A lineáris függésről ill függetlenségről alább még lesz szó.) • A lineáris kombinációk között mindíg előfordul a 0 vektor. • A vektorok összeadásakor a megfelelő komponenseik mod 2 összegét (= átvitel nélküli összegét) képeztük. • Ha a kiindulásként megadott vektorok között előfordult volna a 0 vektor, akkor nem tudtuk volna a vektortérnek mind a 8 vektorát előállítani. • Hasonlóképp, ha pl. a v3 vektor az első kettő összege lett volna (azaz tőlük nem független): v3 = 01101, akkor szintén nem tudtuk volna a vektortérnek mind a 8 vektorát előállítani a lineáris kombinációkkal. D 17 definició: A lineáris függőség és függetlenség Egy vektorhalmaz vektorai lineáris függőségben vannak, ha közülük egy vagy több is előállítható a többi vektor lineáris

kombinációjaként. Ha egy adott vektorhalmaz egyetlen vektora sem állítható elő a többi vektor lineáris kombinációjaként, akkor az adott vektorhalmaz vektorai lineárisan függetlenek egymástól. A fenti P 24. példa kiindulásaként megadott három vektor egymástól lineárisan független volt, mert egyiket sem lehetett a másik kettő semmilyen lineáris kombinációjaként előállítani D 18 definició: A vektorteret kifeszítő vektorhalmaz G = {v1, v2, . ,vn} vektorhalmazt, amely elemeinek lineáris kombinációi előállítják egy V vektortér valamennyi vektorát. Ekkor azt mondjuk, hogy a G halmaz vektorai kifeszítik a V vektorteret. Tekintsünk egy olyan A „kifeszítés” szót itt olyan értelemben használjuk, ahogyan pl. egy háromdimenziós koordinátarendszer (tengelyeire rajzolt egységvektorok) meghatároznak egy háromdimenziós teret. Vegyük észre, hogy ez a definició (még) nem írja elő azt, hogy a vektorainak lineárisan függetleneknek

kell lenniük. G vektorhalmaz 46 P 25. Példa: Vektortér kifeszítése Legyenek az a1; a2; a3; a4, skalárok a GF(2) beli, tehát csakis két értéket felvehető elemek és a V4 vektortér vektorai közül legyenek adottak a következők: v1 = 1 0 0 0 1 v2 = 1 1 1 0 0 v3 = 1 0 0 1 1 v4 = 0 1 1 0 1 Képezzük e vektorok összes lineáris kombinációját! Mielőtt ezt megtennénk, hasonlítsuk össze ezt a feladatot a P 24. példával Látható, hogy az első három vektor megegyezik az ott megadottakkal és a P 24. példa megoldása során kiderült az is, hogy az első három vektor lineáris kombinációi között előfordult a v1 + v2 = 0 1 1 0 1 vektor, ami itt éppen a v4 vektor. Ebben az esetben tehát a kiinduló vektorhalmaz vektorai között van olyan, amelyik a többi lineáris kombinációjaként előállítható, tehát nem teljesül a lineáris függetlenség. Ha az Olvasó veszi a fáradságot és az előző példában megmutatott módszerrel kiszámítja a

fenti négy vektor 24 =16 lineáris kombinációját, akkor látni fogja, hogy e példa vektortere megegyezik a P 24. példa V3 vektorterével, mert itt sem lesz 8-nál több, különböző vektor. (Némelyik ismétlődik majd) Ilyenkor azt mondjuk, hogy a V vektorteret kifeszítő G halmaz redundáns. Ha eltávolítjuk belőle a redundáns (= a többitől lineárisan függő) vektort vagy vektorokat, akkor a megmaradt, egymástól lineárisan független vektorok is ugyanazt a vektorteret feszítik ki, mint a redundáns vektorhalmaz. D 19 definició: Egy vektortér bázisa vagy generátora Többféle G vektorhalmaz is kifeszítheti ugyanazt a V vektorteret. E kifeszítő halmazok közül a V vektortér bázisának vagy generátorának nevezzük azt (vagy azokat) amely(ek) kardinalitása minimális. Ebből a definicióból azonnal következik, hogy a bázis elemeinek lineárisan függetleneknek kell lenniük. A bázis nem lehet redundáns A bázis (vagy, más szóval, generátor)

vektorait bázisvektoroknak nevezzük. Egy V vektortérnek többféle bázisa is lehet. Ez abból következik, hogy egy vektortér összes (bináris esetben 2n) eleme közül többféleképpen is kiválasztható n egymástól független bázisvektor. Ugyanannak a kardinalitású. V vektortérnek valamennyi, egymástól különböző bázisa azonos Mindegy, hogy milyen sorrendben, de egy V vektortér bázisvektorait egy mátrix soraiként is felírhatjuk Ezt a mátrixot generátormátrixnak nevezzük. 47 P 26. Példa: Vektortér generátormátrixa és bázisvektorai A P 24. példában megadott következők voltak: V3 vektortér lineárisan független bázisvektorai a v1 = 1 0 0 0 1 v2 = 1 1 1 0 0 v3 = 1 0 0 1 1 Ezeket egy mátrixban is felsorolhatjuk:  v1  1 0 0 0 1   G = v2  = 1 1 1 0 0 v  1 0 0 1 1   3  Ez a példa V3 vektorterének generátormátrixa. A kardinalitása 3, mert három bázisvektora van Megtehetjük

azonban, hogy a P 24 példában már kiszámolt 8 vektor közül másik három, egymástól lineárisan független vektort választunk ugyanennek a V3 vektortérnek a bázisául: u1 = 0 1 1 1 1 u2 = 0 0 0 1 0 u3 = 1 1 1 1 0 Ezek a V3 vektortér egy, az előbbitől különböző bázisát adják.  u1  0 1 1 1 1   G 2 = u 2  = 0 0 0 1 0 u 3  1 1 1 1 0     A kardinalitás, persze, itt is 3. D 20 definició: Egy vektortér dimenziója V vektortérnek a bázisa k darab bázisvektorból áll, akkor a V vektortér k dimenziós. A jelölése: dim(V ) = k Ha egy 48 T 7 tétel: Bármely V -beli vektor egyedi reprezentációja Legyen egy V vektortér bázisa a következő, k elemű vektorhalmaz: {v0, v1, . ,vi, ,vk-1 } Legyenek továbbá az a0, a1,. ,ai, ,ak-1 skalárok mind az F skalártest elemei. Bizonyítható, hogy minden v  V vektornak létezik egy, és csakis egy v = a0 v0 + a1 v1 +. + ai vi + + ak-1 vk-1

reprezentációja Megjegyzés: A P 24. példa nem bizonyítja ugyan ezt a tételt de legalább demonstrálja F test feletti k dimenziós V vektortérre. A fenti tétel értelmében ebben az esetben minden V-beli v vektor, azaz Gondoljunk egy ∀v  V felírható egy olyan v = a0 v0 + a1 v1 +. + ai vi + + ak-1 vk-1 lineáris kombinációként, amelyben az a0, a1,. ,ai, ,ak-1 skalárok mind elemei F-nek, azaz csakis F-beli értékeket vehetnek fel. 44 V-beli vektornak megfeleltethető egy-egy egyedi szám n-es, amelynek elemei az F-beli skalárok. Következésképp a V vektortér vektorainak számossága egyezik az F feletti szám n-esek számosságával. 45 Imígyen minden Bináris skalárok esetén a k elemű bináris szám n-esekből 2k különböző létezik, tehát a V vektortér elemeinek száma (= kardinalitása) is 2k. A gyakorlati alkalmazásoknál az a lényeg, hogy kölcsönösen egyértelmű leképezés van a k dimenziós V vektortér vektorai és a k-elemű

generátormátrixszal előállítható 2k bináris kódszókészlet között, vagyis egyik a másiknak megfeleltethető. 44 Ha az F test t örténetesen a kételemű GF(2), akkor a s kalárok c sakis k ét ( bináris) ér téket vehetnek fel 45 Ezekből az n elemű bináris szám n-esekből 2n-nél k evesebb i s l ehet, ha a n ekik megfeleltethető vektortér „csak” k < n dimenziós 49 A P 24. példában pontosan azt láthattuk, hogy az ott megadott bináris számötösökből 3 bázisvektorral 23 = 8 elemű vektorteret, ill, a neki megfeleltethető 8 elemű kódszókészletet tudtunk generálni, jóllehet az ötbites kódszavakból összesen 25 = 32 létezhet. Pontosan az itt a lényeg, hogy a hibavédelmi kódok esetében nem minden kódszó megengedett, hanem úgy választjuk ki az összes elvileg lehetséges (bináris) kódszavak halmazából a megengedett 46 kódszavak halmazát, hogy ahhoz valamilyen matematikai modell legyen hozzárendelhető, amelynek a belső

törvényszerüségeit a hibavédelemnél előnyösen tudjuk hasznosítani. A vektortér-modell ilyen kedvező tulajdonságú modell, amit a lineáris blokk kódoknál hasznosítani is fogunk D 21 definició: Az altér Vn vektortér vektorai közül kiválasztható egy olyan Vk vektor-halmaz, amelyre teljesül a vektorterek minden kritériuma, akkor Vk a Vn vektortér altere és Ha egy Vk ⊆ Vn Értelemszerű, hogy a Vk altérnek sem a dimenziója, sem a kardinalitása nem lehet nagyobb, mint a Vn téré, amelyből kiválasztottuk, tehát k ≤ n. Ugyanúgy létezik a valódi és nem valódi altér fogalma, mint a halmazok esetében a valódi és nem valódi részhalmazoké. Egy Vn vektortérnek több (valódi) altere is létezhet és nem kell, hogy ezek egymással megegyezzenek. Mivel egy vektortérnek szükségképpen eleme a zérus vektor, az mindegyik altérnek is eleme kell, hogy legyen. Így Vn különböző altereinek van legalább egy közös vektora: a zérus vektor.

Ezért nem állítható, hogy a különböző alterek diszjunktak lennének. 46 azaz a kódolt kommunikáció során hibátlannak tekintett 50 T 8 tétel az alterekre Legyen S az F test feletti V vektortér egy részhalmaza, azaz S⊆V és jelölje v1 és v2 az S részhalmaz két tetszőleges vektorát, azaz v1 ∈ S és v2 ∈ S S vektortér akkor és csakis akkor altere az F test feletti V vektortérnek, ha v1 -nek és v2 -nek bármilyen lineáris kombinációja is S -beli vektor, azaz bármilyen α, β ∈ F-re Az α.v1 + βv2 ∈ S A D 21. definició azt állította az S altérről, hogy arra „teljesülnie kell a vektorterek minden tulajdonságának”. Nos ez így nem valami precíz meghatározás A T8 tétel leszűkíti ezt az általános megfogalmazást arra, hogy az S altér bármely két vektorának lineáris kombinációja is eleme kell, hogy legyen ugyanannak az S altérnek. Vegyük észre, hogy ebből a definicióból következik, hogy a zérus vektor

szükségképpen eleme minden altérnek, mert az úgy is felfogható, mint egy vektornak saját magával alkotott összege. A fenti tétel pedig nem írja elő, hogy a v1 és a v2 vektoroknak feltétlenül különbözőeknek kell lenniük D 22 definició: A belső szorzat Legyenek u és v az F test feletti V vektortér vektorai u = ‹u0; u1; ,. ; un-1› V v = ‹v0; v1; ,. ; vn-1› V Az u  v un. belső szorzatot a következőképp definiáljuk: n uv= ∑u v i =1 i i = u0.v0 ⊕ u1v1 ⊕ ⊕ uivi ⊕ ⊕un-1vn-1 A belső szorzás tehát olyan kétargumentumos művelet, amelynek mindkét operandu- V vektortérből származó vektor, az eredménye viszont az F testből való skalár. A szummázást az F test feletti (1.sz) additív művelettel kell elvégezni, ahogyan azt a sa a 43. oldalon látható „családfán” is ábrázoltuk 51 Az előzőekben megadott definició alapján a belső szorzat a következő tulajdonságokkal rendelkezik: 1.

Kommutatív, azaz uv=vu 2. A skalárral való szorzással asszociatív, azaz a . (u  v) = (a u)  v 3. A vektor összeadással disztributív, azaz u  (v + w) = (u  v) + (u  w) A belső szorzattal együtt tehát összesen négy műveletet definiáltunk az F test feletti V vektortér felett. Ezekből kettő additív, kettő pedig multiplikatív művelet Mindegyikre más-más műveleti jelet vezettünk be. Az additív műveletek közül a ⊕ művelet csak az F test felett van értelmezve, a vektorok összeadására bevezetett művelet pedig a V vektortér felett. A multiplikatív műveletek közül az elsőt .-tal jelöltük és egy + V-beli vektornak egy F- beli skalárral való szorzását jelentette. Az eredménye egy V -beli vektor volt Az imént V-beli vektorpárokon van értelmezve és az eredménye egy F-beli skalár. A kiszámításánál az F test feletti bevezetett belső szorzásra a  jelet vezettük be. Ez a szorzás additív műveletet is

alkalmazni kell. Megjegyezzük még, hogy a belső szorzatot a vektoralgebrában skalárszorzatnak is szokták nevezni, mert az eredménye egy skalár. 52 D 23 definició: Duális vektorterek V vektortér egy k dimenziós (k<n) valódi alterét S és az S altér ugyancsak V-beli duális párját az S altér 47. (Egyelőre semmit sem mondunk arról, hogy S hány dimenziós.) S ⊂ V és S ⊂ V Jelölje egy n dimenziós S altér egy tetszőleges vektorát u ∈ S és jelölje az S altér egy tetszőleges vektorát v ∈ S . Természetesen u, v ∈ V Jelölje továbbá az Az S altér akkor, és csakis akkor duális párja 48 az S altérnek, ha minden u  v = 0 Az Olvasó kisérelje meg elképzelni, hogy egy 3 dimenziós koordinátarendszer tengelyei által kifeszített térnek létezik egy az x és az y tengelyek által kifeszített, kétdimenziós altere (ti. az xy koordináta-sík) és ennek duális altere a z tengely által „kifeszített”

egydimenziós altér Az utóbbi minden vektora merőleges az xy sík minden vektorára (ha a zérus vektorokról elfeledkezünk). Vannak esetek, amelyeknél sokkal könnyebb egy vektorteret, vagy annak a tulajdonságait a duális párjával leírni, mintsem magával a vektortérrel. Erre sok példa található a lineáris blokk kódok körében Ismételten felhívjuk az Olvasó figyelme arra, hogy az S altér és a duális S┸ altér nem diszjunkt halmazok, mert mindkettő egyaránt tartalmazza legalább a zérus vektort. Létezik olyan eset is, amikor egy altérnek saját maga a duális párja. A következő három tétel a dulis altér-párok viszonyát hivatott leírni. T 9 tétel az alterek viszonyára Az S ⊆ V altér duális párja eltekintünk.) S ⊆ V maga is vektortér. (A bizonyítástól itt is 47 A furcsa, felső index egyfajta, az ortogonalitáshoz (=merőlegességhez) hasonló tulajdonságra utal, mintha S minden vektora merőleges lenne S minden vektorára,

de erről azért nem lehet szó, mert mind S mind S vektorterek, tehát mindkettőnek eleme a zérus vektor, azzal kapcsolatban pedig nem értelmezhető az ortogonalitás. 48 Néha S duális alterének, néha pedig S nullterének is nevezik. 53 T 10 tétel a dimenziók viszonyára Legyen S ⊆ V egy véges dimenziójú altere V-nek és legyen S duális párja az S ⊆ V altér. Bizonyítható, hogy dim (S ) + dim (S ) = dim (V ) (A bizonyítástól itt is eltekintünk.) A tételből következik, hogy ha a ( k ≤n ), akkor az S  V vektortér n-dimenziós és az S altér k-dimenziós altérnek n-k dimenziósnak kell lennie. T 11 tétel a kardinalitások viszonyára Nyilvánvaló, hogy a V vektortér és duális párt alkotó S és S altereinek kardinalitásai között is van összefüggés: a duális altér-páros kardinalitásainak szorzata (és nem az összege!) az, ami egyenlő a V vektortér kardinalitásával, azaz card (S ) . card (S ) = card (V )

(A tétel a kardinalitások logaritmusainak összegével is megfogalmazható.) P 27. Példa: Egy V7 vektortér valódi S4 altere és annak duális párja Adott egy n = 7 dimenziós V7 vektortér S4 alterének egy bázisa a következő generátormátrixszal: 1 0 G= 0  0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1  b1  1 b 2  = 0  b 3     1 b 4  Vegyük észre, hogy ennek a generátornak a baloldali 4 X 4 –es négyzetes mátrixa egy k=4-ed rendű egységmátrix. Az ezzel generált kódot szisztematikus kódnak is szokták nevezni és az ilyen felépítésű generátort kanonikus generátornak. 49 A baloldali egységmátrix miatt nyilvánvaló, hogy a kanonikus generátor bázisvektorai lineárisan függetlenek. 49 Emlékezzünk arra, hogy végül is mindegy, hogy a bázisban milyen sorrendben írjuk a bázisvektorokat, tehát egy G generátorból a generátormátrix sorainak cseréjével (esetleg)

kanonikus generátort is előállíthatunk. Másrészt emlékezzünk arra is, hogy egy kódnak többféle generátora is l étezhet és h a az éppen m egadott g enerátor n em kanonikus, az nem jelenti azt, h ogy az adott vektortérnek nem is lehet kanonikus generátora. Tény azonban, hogy kanonikus generátor nem mindíg létezik 54 A megadott G generátornak 4 bázisvektora van, tehát 24 = 16 elemű S4 alteret generál úgy, hogy képezzük a bázisvektorok valamennyi lineáris kombinációját. a kódszó vagy vektor Hamming súly 50 = 0 0000000 0 b4 = b4 0001111 4 b3 0 = b3 0010110 3 0 b3 b4 = b3+b4 0011001 3 0 b2 0 0 = b2 0100101 3 0101 0 b2 0 b4 = b2+b4 0101010 3 6 0110 0 b2 b3 0 = b2+ b3 0110011 4 7 0111 0 b2 b3 b4 = b2+ b3+b4 0111100 4 i a1a2a3a4 a1b1 + a2b2+ a3b3+ a4b4 = 0 0000 0 0 0 0 1 0001 0 0 0 2 0010 0 0 3 0011 0 4 0100 5 vi 3 8 1000 b1 0 0 0 = b1 1000011 3 9 1001 b1 0 0 b4

= b1 +b4 1001100 3 10 1010 b1 0 b3 0 = b1 + b3 1010101 4 11 1011 b1 0 b3 b4 = b1 + b3+b4 1011010 4 12 1100 b1 b2 0 0 = b1 + b2 1100110 4 13 1101 b1 b2 0 b4 = b1 + b2+b4 1101001 4 14 1110 b1 b2 b3 0 = b1 + b2+ b3 1110000 3 15 1111 b1 b2 b3 b4 = b1+ b2+b3+b4 1111111 7 Amint várható is volt, a 4 db bináris bázisvektor 24 = 16 elemű k=4 dimenziós alteret generál. Ezt az alteret jelöljük S4 –gyel. Ez az altér valódi részhalmaza a V7 vektortérnek. A 7 dimenziós V7 -nek egyébként 27 = 128 vektora kell, hogy legyen S4 altér duális párja a T 10 tétel értelmében 3 dimenziós kell, hogy legyen. Ezért 3 olyan bázisvektorának kell lennie, amelyek mindegyike lineárisan független az S4 Az altér vektoraitól. Érdemes megfigyelni, hogy a fentiekben generált S4 altérben nincs 3-nál kisebb Hamming súlyú vektor (ill.kódszó) Ennek alább jelentősége lesz 50 Egy bináris kódszó un. Hamming súlya a

kódszóban lévő 1-es jegyek száma 55 A duális S3 altér bázisvektorait (elvileg) úgy választhatjuk ki, hogy képezzük a V7 - S4 vektorhalmazt (amelynek az előbbiek szerint 128-16 = 112 vektora van) és ezek közül kiválasztunk 3, egymástól lineárisan független bázisvektort az S3 duális altér generálásához. A V7 – tér a következő vektorokat tartalmazza: i kód i kód i kód i kód 0 0000000 32 0100000 64 1000000 96 1100000 1 0000001 33 0100001 65 1000001 97 1100001 2 0000010 34 0100010 66 1000010 98 1100010 3 0000011 35 0100011 67 1000011 99 1100011 4 0000100 36 0100100 68 1000100 100 1100100 5 0000101 37 0100101 69 1000101 101 1100101 6 0000110 38 0100110 70 1000110 102 1100110 7 0000111 39 0100111 71 1000111 103 1100111 8 0001000 40 0101000 72 1001000 104 1101000 9 0001001 41 0101001 73 1001001 105 1101001 10 0001010 42 0101010 74 1001010 106 1101010 11

0001011 43 0101011 75 1001011 107 1101011 12 0001100 44 0101100 76 1001100 108 1101100 13 0001101 45 0101101 77 1001101 109 1101101 14 0001110 46 0101110 78 1001110 110 1101110 15 0001111 47 0101111 79 1001111 111 1101111 16 0010000 48 0110000 80 1010000 112 1110000 17 0010001 49 0110001 81 1010001 113 1110001 18 0010010 50 0110010 82 1010010 114 1110010 19 0010011 51 0110011 83 1010011 115 1110011 20 0010100 52 0110100 84 1010100 116 1110100 21 0010101 53 0110101 85 1010101 117 1110101 22 0010110 54 0110110 86 1010110 118 1110110 23 0010111 55 0110111 87 1010111 119 1110111 24 0011000 56 0111000 88 1011000 120 1111000 25 0011001 57 0111001 89 1011001 121 1111001 26 0011010 58 0111010 90 1011010 122 1111010 27 0011011 59 0111011 91 1011011 123 1111011 28 0011100 60 0111100 92 1011100 124 1111100 29 0011101 61 0111101 93 1011101 125

1111101 30 0011110 62 0111110 94 1011110 126 1111110 31 0011111 63 0111111 95 1011111 127 1111111 56 A V7 – tér vektorai közül áthúztuk azokat, amelyek az S4 altérnek is elemei. Tehát a nem áthúzott vektorok közül kell három, egymástól lineárisan független vektort kiválasztani az S3 duális altér generálásához. Ez,persze, többféleképpen is lehetséges, ami azt (is) jelenti, hogy az S4 altérnek több, különböző duális párja is lehet V7 – ben, de ezek mindegyike 3 dimenziós. Az előző táblázatban megjelöltük a duális altér bázisvektoraikén kiválasztott (75, 39, és 23 indexű) vektorokat. ezekkel a következő generátor írható fel 51 1 0 0 1 0 1 1 b 5  G = 0 1 0 0 1 1 1 = b 6  0 0 1 0 1 1 1 b 7  Ezzel a generátorral a már ismert módszer szerint a következő, háromdimenziós altér generálható: a kódszó vagy vektor Hamming súly = 0

0000000 0 b7 = b7 0010111 4 b6 0 = b6 0100111 4 0 b6 b7 = b6+b7 0110000 2 100 b5 0 0 = b5 1001011 4 5 101 b5 0 b7 = b5+b7 1011100 4 6 110 b5 b6 0 = b5+ b6 1101100 4 7 111 b5 b6 b7 = b5+ b6+b7 1111011 6 j a5a6a7 a5b5 + a6b6+ a7b7+ = 0 000 0 0 0 1 001 0 0 2 010 0 3 011 4 uj Ennek az S3 altérnek csak egyetlen közös eleme van az a 0000000 vektor. S4 altérrel, nevezetesen n-k = 7-4 = 3 dimenziós vektortér lévén összesen 23 = 8 vektora van (a zérus vektort is beleértve). V7 – vektortér vektorainak előbbi táblázatában a szürke mezőkkel már megjelölt bázisvektorokon kívül kettős áthúzással jelöltül az S3 altér vektorait. A 51 Úgy v álasztottuk k i a báz isvektorokat, ho gy a ge nerátor bal oldali 3 x 3 -as al mátrixa egy ségmátrix legyen, tehát ez a generátor is kanonikus. 57 Az S4 altérnek 16 vektora van, a duális S3 párjának pedig 8 vektora és mindkét altér

tartalmazza a zérus vektort. A kardinalitások szorzata 8 x 16 = 128, ami megegyezik a volt. V7 – tér kardinalitásával, amint az a T 11. tétel értelmében várható is V7 – tér vektorai között egy csomó olyan van, amelyik sem az S4 altérnek, sem pedig a duális S3 altérnek nem eleme. Vegyük észre, hogy a A belső szorzatra vonatkozó D 22. definició szerint az S3 duális altér bármelyik vektorát szorozzuk az S4 altérnek bármelyik vektorával, a belső szorzatnak nullát kell adnia. Próbáljuk ki! Válasszuk ki véletlenszerűen 52 az S4 altérből pl. az i=14-es indexű v14 = 1110000 vektort, az S3 altérből pedig a j=6-os indexű u6 = 1101100 vektort. Ezek belső szorzata: v14  u6 = 1.1 ⊕ 11 ⊕ 10 ⊕ 01 ⊕ 01 ⊕ 00 ⊕ 00 = 1 ⊕ 1 = 0 A belső szorzatuk tehát 0, ami más szóval azt is jelenti, hogy a két vektor egymásra merőleges. Az ortogonalitás-vizsgálat, persze, akkor teljes, ha az S3 altér valamennyi vektorával

elvégezzük a vizsgált v14 vektor belső szorzását és a szorzat eredménye minden esetben 0. Szerencsére nem szükséges ilyen sok szorzást elvégezni, mert az S3 alteret tökéletesen „képviselik” (mint korábban mondtuk: „kifeszítik”) a bázisvektorai. No és mi van akkor, ha egy olyan V7 – beli vektort viszgálunk, amely sem S4 –nek, S3 altérnek nem eleme? Próbáljuk ki ezt is, de most végezzük el a találomra kiválasztott vektor belső szorzását az S3 altér mindhárom bázisvektorával! sem az Válasszuk pl. a V7 tér 87-es indexű vektorát,: v87 = 1010111 Az S3 altér bázisvektorai pedig rendre u4 = 1001011, u2 = 0100111, u1 = 0010111, v87  u4 = 1.1 ⊕ 00 ⊕ 10 ⊕ 01 ⊕ 10 ⊕ 11 ⊕ 11 = 1 ⊕ 1 ⊕ 1 = 1 v87  u2 = 1.0 ⊕ 01 ⊕ 10 ⊕ 00 ⊕ 11 ⊕ 11 ⊕ 11 = 1 ⊕ 1 ⊕ 1 = 1 v87  u1 = 1.0 ⊕ 00 ⊕ 11 ⊕ 00 ⊕ 11 ⊕ 11 ⊕ 11 = 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0 52 A két altér zérus vektorait zártjuk ki ebből a

véletlenszerű választásból. E kizárás okát többféleképpen i s m egfogalmazhatjuk: E gyrészt a z érus v ektorokat tekinthetjük a belső szorzat, mint művelet, zérus elemeinek. Más, szemléletesebb megfogalmazásban mondhatjuk azt is, hogy ha a belső szorzattal két vektor ortogonalitását vizsgáljuk, akkor ezek közül egyik sem lehet a zérus v ektor, m ert a nul la k iterjedésű „vektorra” nem értelmezhető az, hogy hozzá képest bármely más vektor merőleges-e vagy sem. 58 Figyelemre méltó, hogy az S3 altérnek van olyan bázisvektora, amelyre merőleges a vizsgált v87 vektor. (Az adott esetben u1) Tudjuk azonban, hogy az minden vektora (az egy zérus vektort kivéve) merőleges az S  3 S4 altérnek altér minden vekto- rára (az egy zérus vektort kivéve), mert az S4 altérnek duális párja az S3 altér. Akkor, és csakis akkor lehetünk biztosak abban, hogy a vizsgált v vektor az S4 altér eleme ha egy ilyen módon vizsgált v

vektornak az S3 altér valamennyi bázisvektorával képzett belső szorzata 0. A lineáris csoportkódoknál úgy alkalmazzuk ezt hibavédelemre, hogy hibátlan (vagy ―más szóval― „megengedett”) kódszavaknak tekintjük egy Sk (k-dimenziós) altér vektorait és úgy vizsgáljuk meg, hogy valamilyen v vektor a megengedett kódszavak közé tartozik-e, hogy rendre képezzük a v vektor és az Sn-k (n-k-dimenziós) nulltér 53 bázisvektorainak belső szorzatait. Sn-k altér valamennyi bázisvektorára merőleges, akkor, és csakis akkor, magára az egész Sn-k altérre is merőleges. Ha a v vektor az 53 Korábban m ár m egjegyeztük, h ogy az azaz az S  n-k Sk (k-dimenziós) al tér ( n-k) di menziós duális p árját, alteret nulltérnek is nevezzük. Most már érthető, hogy azért, mert valamennyi bázisvektorának belső szorzata az Sk altér bármelyik vektorával 0. 59 5 A Galois testek alapvető tulajdonságai. Ebben a fejezetben a Galois

testek és az azokat alkotó elemek alapvető tulajdonságaival foglalkozunk. Az a legelső dolog, amit meg kell említeni, hogy az algebrai csoporttól eltérően a Galois test rendje teljesen meghatározza magát a testet Következésképp két, azonos rendű Galois test mindíg azonos, függetlenül attól, hogy esetleg nagyon különbözőképp állítjuk elő a két testet. Ez az azonosság (pontosabban: izomorfizmus) egészen a test elemeinek cimkézéséig teljesül Ezért aztán nem azt mondjuk, hogy egy GF(q), hanem teljesen félreérthetetlen, ha a GF(q)-ról beszélünk. Jelöljük β-val GF(q) egy elemét és jelölje 1 a multiplikatív egységelemet. Tekintsük ezek után a GF(q) elemeinek következő sorozatát: 1, β, β2, β3, β4, β5, . Mivel β ∈ GF(q), ezért β valamennyi egymás után következő egész hatványa is eleme kell, hogy legyen GF(q)-nak, (mivel a test feletti multiplikatív művelet zárt). Másrészt viszont GF(q) elemszáma véges és ez

csak úgy lehetséges ha β hatványainak előbbi sorozata egy pont után úgy folytatódik, hogy a következő elemek már mind olyanok, amelyek korábban már előfordultak. Könnyen belátható, hogy az első ismétlődő elemnek az 1-nek kell lennie. Gondoljuk végig az alábbi követkaztetést! Tegyük fel, hogy β már előfordult a sorozatban és az először megismétlődő elem β y x éppen β -nal egyenlő és nem állítjuk, hogy β egyenlő az egységelemmel, azaz y x βx = βy és 0 < y < x 60 Az ismétlődő szakasz első tagjának, azaz β -nek feltétlenül elő kell fordúlnia az első szakasz tagjai között, hiszen éppen ez jelenti azt, hogy ismétlődik. Az első szakasz y eme ismétlődő elemét jelültük β -nal, az ismétlődő szakasz első elemét pedig βx-nel. x Nem kötjük ki, hogy az első hatványsorozat melyik eleme az, amit β -nal jelöltünk, csak azt, hogy forduljon elő ez a hatvány az első sorozatban. y Az ismétlődő sorozat

első eleme tehát βx = βy Mivel β is és β is egész hatványa β–nak, ezért β maradék nélkül osztható β -nal. x y x y A hányadosuk βx / βy = βx-y és nyilvánvaló az is, hogy egy 1, β, β2, β3, β4, β5, . , βy , , βx  ez a sorozat első része hatvány sorozat bármelyik tagjának oszthatónak kell lennie bármely megelőző taggal, x így β -nek a sorozat első részének valamennyi tagjával. Ha β = β (mint feltételeztük), akkor x=y és β / β = β = β = 1 és ez kell, hogy legyen az ismétlődő sorozat első tagja, vagyis a sorozat ismétlése csakis a x y x y x-y 0 βx= β0= 1 elemmel kezdődhet. D 24 definició: A Galois test egy elemének a rendje Legyen β a GF(q) egy eleme. β rendje az a legkisebb pozitív m egészszám, amelyre β = 1 jelölése a következő: ord ( β ) m Ez a definició azonos a csoport egy eleme rendjének a definiciójával (Ld. a D9 definiciót a 24 oldalon)

Meg kell azonban jegyezni, hogy egy Galois test elemeinek rendje esetében az elem rendjének meghatározásakor a multiplikatív műveletet és nem az additív műveletet vesszük figyelembe. A Galois test nemzérus elemeinek ugyanúgy jól meghatározott rendjük van, mint a csoportok esetében. A Galois testeknél azonban igen szigorú kritériumokat kell, hogy kielégítsen az elemek rendje Először is azt, hogy a GF(q) Galois test bármelyik β eleme osztója kell, hogy legyen (q-1)-nek. 61 T 12 tétel: GF(q) osztóinak alcsoportja Ha valamely tetszőleges β ∈ GF(q) esetén ord ( β ) = t akkor t | (q-1) Ha valamely β ∈ GF(q) esetén β = 1és t = ord ( β ) akkor a t {β, β , β , β , β , . , β } a GF(q) nemzérus elemeinek egy a multiplikatív művelet alatti alcsoportját alkotja. Ez a Lagrange tételből (Ld T 4) következik Ez tulajdonképpen a T 12 tétel bizonyítása. 2 3 4 5 t A T 12 tétel következménye az alábbi T 13 tétel: a legnagyobb

közös osztó (LNKO) Az i és a j egészszámok legnagyobb közös osztója: LNKO( i, j ) az a legnagyobb m egészszám amely maradék nélkül osztja mind i-t, mind j-t: m | i és m | j. T 14 tétel GF(q) elemeinek LNKO-ja Legyen mind α mind β eleme GF(q) –nak és legyen β = αi Ha ord ( α ) = t akkor ord ( β ) = t / LNKO (i , t) (A bizonyítástól ismét eltekintünk.) A T 12 tétel meghatározza, hogy egy véges test elemei egyáltalán milyen rendűek lehetnek. Például a GF ( 16 ) test elemeinek rendje 1, 3, 5, és 15 lehet, mert a T 12 tétel értelmében az elemek rendje osztója kell, hogy legyen (16-1)-nek. 54 Más kérdés, hogy hány darab adott rendű eleme van GF( q )-nak. Ezt az információt egy különlegesen hatékony függvény adja meg nekünk, amely szerepet kap a Galois testek elméletében mindenütt és még azon kívül is, a számelmélet határán is. Ez a különleges függvény (amit mindjárt definiálunk is) központi „magja” a

legnépszerűbb nyiltkulcsú kriptorendszernek, nevezetesen az RSA rendszernek is. D 25 Definició: Az Euler-féle Φ függvény Definiáljunk egy olyan {1, . .,t-1} halmazt amelynek mindegyik eleme relatív prímszám a t egészszámhoz képest. A Φ(t) függvény megadja e halmaz elemeinek számát., ha t > 1 Definició szerint Φ(1) = 1; Ezt a szóbeli definiciót képletben is megadhatjuk. Építsük fel ezt a képletet! 54 Figyeljük meg, hogy a nem valódi osztókat [ti. 1-et és (q-1)-et] is felsoroltuk Ennek alább majd jelentősége lesz, amikor tételt adunk meg arra, hogy hány osztója lehet egy galois testnek. 62 Ha egy i egészszám és az adott t szám relatív prímek, akkor a legnagyobb közös osztójuk 1, azaz LNKO( i, t ) = 1. Vegyük mindazon 0-nál nagyobb, de t-nél kisebb i egészszámok halmazát, amelyek t-re nézve relatív prímek, azaz LNKO(i, t) = 1. Ez a halmaz a következő: {1 ≤ i < t | LNKO (i, t) = 1}; Az egészszámok e halmazának a

számossága (=kardinalitása) adja meg az Eulerféle Φ(t) függvény értékét. A definicióból következően Φ(t) értéke csakis pozitív egészszám lehet, s mint állítottuk definició szerint Φ(1) = 1. Következésképp Φ(t) = card ({1 ≤ i < t | LNKO (i, t) = 1}) Φ(t) értékének a kiszámítására alkalmas a következő képlet is: Jelölje p a t-nél kisebb bármelyik pozitív prímszámot, amely t-nek osztója azaz p|t. Ezzel minden t > 1 értékre a következő összefüggéssel lehet Φ(t) értékét kiszámítani:  1 Φ (t ) = t.∏ 1 −  p p |t  Némely matematikai szövegben ezt a függvényt Euler-féle súlyfüggvénynek 55 is nevezik. P 28. Példák: Az Euler-féle Φ(t) függvények kiszámítására P.281 Φ(56) kiszámításához vennünk kell minden olyan egészszámot, amely 1nél nagyobb (vagy 1-gyel egyenlő) de kisebb 56-nál és 56-hoz képest relatív prímszám. Számítsuk ki ehhez először is 56

törzstényezőit: 56 = 2.227, tehát minden olyan 56-nál kisebb szám, amely törzstényezői között e törzstényezők előfordulnak, nem relatv prím 56-hoz képest. természetesen a 2 és a 7 prímszámokon kívül valamennyi 56-nál kisebb prímszám is relatív prímje 56-nak. Az utóbbi prímek a következők: 1, 3, 5, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 56 Ezek prímszámok és van belőlük összesen 15 db. 55 az angol terminológiában „totient function”, s a „ totient” szó összeget is jelent, ami a def inició szerinti relatív prímek számának összegére utal. 56 Abszolute n em ny ilvánvaló, hogy a prímek k özött 1-et is f el k ell s orolni, t i. ez n em is r elatív prímje semmilyen pozitív t egészszámnak és nem is valódi osztó. A definició szerinti Φ(1) = 1 miatt azonban mindíg fel kell sorolni a megszámolandó prímek között az 1-et is. 63 Nem szerepelnek közöttük az alábbi összetett számok, amelyek azonban

relatív prímek 56-hoz képest, mert nincsenek 56-éval közös törzstényezőik: 9, 15, 25, 27, 33, 39, 45, 51, 55 amelyekből, mint látjuk, összesen 9 darab van. Ezek szerint Φ(56) = 15 + 9 = 24 Számoljuk ki Φ(56) értékét a másik, produktumos képlettel is! Φ(56) = 56(1-1/2)(1-1/7) = 56.1/26/7 = 56 ½6/7 = 56 3/7 =24 Ez a számítási algoritmus –mint beláthatjuk- sokkal egyszerűbb, mint a relatív prímek megkeresése, felsorolása és megszámlálása. Figyeljük meg, hogy az utóbbi számításnál nem kellett figyelembe venni, hogy az adott t = 56-os szám egyik prímtényezője (nevezetesen a 2) a harmadik hatványán fordult elő a prímfelbontásban. Csakis azt kellett figyelembe vennünk, hogy hányféle (különböző) prímfaktora van a megadott t = 56nak Kétféle volt: 2 és 7, és csakis ezekkel számoltunk P 28.2: Φ(256) = Φ(28) = 28.(1-1/2) = 27 = 128 P.283 Φ(30) = Φ(2.35) = 30(1-1/2) (1-1/3) (1-1/5) = = 30. ½2/34/5 = 308/30 = 8 Ezt a Φ(30)

értéket speciel nem lenne nehéz kiszámolni a t = 30 szám relatív prímjeinek a megkeresésével sem. A 30-nál kisebb olyan prímek, amelyek nem szerepelnek 30 = 2.35 prímfaktorizációjában (az 1-et is beleértve) a következők: 1, 7, 11, 13, 17, 19, 23, 29, tehát összesen 8 db. Rajtuk kívül nincs is 30-nál kisebb olyan prím, vagy összetett szám, amelynek ne lenne a 30-cal közös törzstényezője. Következésképp Φ(30) =8 Az Euler-féle következnek: Φ függvény alább felsorolt tulajdonságai a definiciós képletekből Φ(p) = p-1, pozitív nemzérus egész relatív prím p-hez képest. • Ha • Φ(p1. p2) = Φ(p1) Φ(p2) = (p1-1) (p2–1), ha p1 és p2 nem azonos p pozitív prímszám, akkor mert minden p-nél kisebb prímek. • Φ(pm) = pm-1.(p-1) • Φ( pm rn) = pm-1 rn-1.(p-1) (r-1) minden p prímszámra. minden p ≠ r prím-párra. 64 T 15 tétel A Galois testek multiplikatív struktúrája Vizsgáljuk a GF(q) Galois testet.

1. Ha t nem osztója (q-1)-nek, akkor a GF(q)-ban nincsenek t-ed rendű elemek. 2. Ha t osztja (q-1)-et, azaz t | q-1, akkor GF(q)-nak eleme van. Φ(t) darab t-ed rendű Bizonyítás: A tétel első része nem más, mint a T12 tétel újra-fogalmazása. Itt azonban (a T 12 tétellel szemben) nem azt hangsúlyozzuk, hogy GF(q) elemeinek rendszámai alcsoportot alkotnak GF(q) alatt annak a multiplikatív műveletére nézve, hanem azt, hogy ha egy t szám nem osztója (q-1)-nek, akkor nincs is t-ed rendű eleme GF(q)nak. A tétel második része is a korábbi tételek következménye. legyen t egy α elem rendje, azaz t = ord(α). Ekkor az { α, α2, , αt } halmaz tartalmazza az xt – 1 = 0 egyenlet valamennyi megoldását, és csakis azokat 57. Ebben a halmazban tehát valamennyi t-ed rendű elemnek benne kell lennie. A T13 és T14 tételek szerint azonban csakis azok az αi alakú elemek lehetnek t-ed rendűek, amelyekre t és i relatív prímek, azaz LNKO( i, t) = 1. Definició

szerint azonban éppen Φ(t) darab ilyen elem van s éppen ez az, amit a fenti tétel második része állít. D 26 Definició: A primitív elem GF(q)-nak minden (q-1)-ed rendű elemét GF(q) primitív elemének nevezzük. A T 15 tétel következménye: Minden véges GF(q) Galois testnek pontosan Φ(q-1) darab primitív eleme van Ennek a következménynek igen nagy a jelentősége akkor, amikor kijelentjük, hogy minden pozitv x egészszám esetén Φ(x) mindíg nagyobb 0-nál. Következésképp minden GF(q) Galois testnek van legalább egy (nemzérus) primitív eleme. Jelöljük GF(q)-nak valamelyik primitív elemét α–val és vizsgáljuk meg a következő sorozatot: 1, α, α2, α3, ,αq-2, αq-1, αq, 57 az egyenlet t-ed fokú és az adott halmaznak éppent darab különböző eleme van. A t-ed fokú egyenletnek pedig éppen t darab gyöke kell, hogy legyen. 65 A primitív elem definiciója szerint a fenti sorozatban α–nak az első olyan pozitív hatványa, ahonnan a

sorozat ismétlődni kezd, éppen αq-1. A test egy eleme rendjéről korábban már leírt gondolatmenetből következik, hogy az első ismétlődő elemnek 1nek kell lennie. Így a fenti sorozatban felírt első (q-1) darab elem mind különböző Mivel ezek egyike sem lehet zérus, ezért a felírt sorozat első (q-1) darab eleme alkotja GF(q) összes, azaz (q-1) darab nemzérus elemét. Ebből aztán egy igen fontos következtetést vonhatunk le. Nevezetesen azt, hogy GF(q) valamennyi nemzérus eleme felírható egy α primitív elem egymást követő (q-1) darab egész hatványaként. P 29. Példa: GF(7) multiplikatív struktúrája Mivel 7 prímszám, a {0, 1, 2, 3, 4, 5, 6} halmaz, valamint a modulo 7 összeadás és szorzás segítségével megszerkeszthetjük GF(7)-et. A mod7 szorzás művelettáblája a következő lesz: ⊙ 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 2 0 2 4 6 1 3 5 3 0 3 6 2 5 1 4 4 0 4 1 5 2 6 3 5 0 5

3 1 6 4 2 6 0 6 5 4 3 2 1 A T 15. tétel következménye szerint a GF(7) Galois test primitív elemeinek a száma Φ(7-1) = 2 kell, hogy legyen. 66 Mivel a primitív elem GF(q)-nak nemzérus eleme és 1-nek bármelyik hatványa 1, ezért csakis a {2, 3, 4, 5, 6} részhalmaz elemei között kell, hogy keressük a két primitív elemet. 58 A mondottak szerint GF(7) egy primitív elemének (7-1) = 6 első hatványa elő kell, hogy állítsa GF(7) valamennyi elemét, Némi próbálgatással rá lehet jönni, hogy a primitív elemek 3 és 5. Állítsuk elő ezek első hat hatványát a mod 7 szorzás művelete szerint: 31 = 3; 32 = 2; 33 = 6; 34 = 4; 35 = 5; 36 = 1; Hasonlóképp a másik primitív elem első hat hatványa a mod 7 szorzás művelete szerint “hatványozva” a következő: 51 = 5; 52 = 4; 53 = 6; 54 = 2; 55 = 3; 56 = 1; A T 14. tétel segítségével már könnyen meghatározhatjuk GF(q) elemeinek rendjét, ha egy elem rendjét ismerjük. Használjuk

erre az “5” primitív elemet: i 5i LNKO(i,6) ord(5i) = 6/LNKO(i,6) 0 1 6 1 1 5 1 6 2 4 2 3 3 6 3 2 4 2 2 3 5 3 1 6 Mivel a 0 bármilyen számmal osztható, ezért 0 és 6 legnagyobb közös osztója a 6. 58 Okoskodhatnánk a következőképp: „Ha a primitív elemek páros számok lennének, azok semmilyen (egész) hatványa nem állíthatná elő a fenti halmaz {2, 4, 6} részhalmazának el emeit.” E z a gond olatmenet az onban hibás, m ert ne m v eszi f igyelembe az i smételt m od 7 szorzás (azaz a mod 7 hatványozás) sajátságait. Ezt könnyű belátni ha, kipróbáljuk a test egy elemén. A 2 eleve páros szám Egyik hatványa a 2 3 = 8 is Igen ám, de ennek a 7-es modulussal számított maradéka 8-7 = 1 páratlan szám Nem igaz tehát, hogy a p áros számok (mod7) hatványai is mind páros számok. A t ermészetes s zámok f elosztása „ páros” és „ páratlan” s zámokra k ülönben i s a m od 2 kongruencia két

maradékosztálya s itt, az adott példának semmi köze a mod 2 kongruenciához. 67 Így érthető, hogy miért került az utolsó oszlop első adatsorába 6/6 = 1. GF(7) nemzérus elemeit az imént az “5” primitív elem első hat 59 hatványának kiszámításával már meghatároztuk. Ezeket tüntettük fel a táblázat második oszlopában Az elemek rendjének kiszámításához azonban a második oszlop egészszámaira nincs szükség. A táblázat második oszlopában felsorolt elemek rendje a táblázat negyedik oszlopában szerepel. Látható, hogy mind a 3-ad rendű, mind a 6-od rendű elemekből 2-2 darab van, míg 1-ső rendű és 2 rendű elem csak egy-egy A GF(7) elemeinek 60 rendjei 61 mint a T 12. tétel alapján várható volt mind osztói q -1 = 7-1 = 6-nak. Nézzük meg most, hogy a 0 < j < 7 rendű elemekből (minden egyes j-hez különkülön) hány van GF(7)-ben: Az elem rendje j A G F(7)-ben létező j-ed rendű elemek φ(j) 1 {1} 1 2 {6} 1

3 {2,4} 2 4 Nincs, me rt 4 n em os ztója 6-nak - 5 Nincs, me rt 5 n em os ztója 6-nak - 6 {3,5} 2 Összesen 59 6 nemzérus elem Mert a példában q = 7 és az első q-1 = 7-1 = 6 hatványt kell kiszámolni. Azt is láttuk a 66 oldal elején l eírt es zmefuttatásban, h ogy a h atvány-sorozat az é ppen αq-1 tagtól ismétlődik és az ismétlődés első eleme éppen 1. Nos, az „5” primitív elem előbbi hatványozásakor „kijött”, hogy a q-1 = 7-1 = 6. hatvány éppen 1, ami pontosan megegyezik a primitív elem 0-adik hatványával Ezért az itt számított táblázatban nem kell az ismétlődő hatványsorozat első elemét (azaz 56 = 1-et) még egyszer figyelembe venni, mert az 50 = 1-gyel már egyszer figyelembe vettük. 60 amelyeket a táblázat második oszlopában soroltunk fel 61 amelyek viszont a táblázat utolsó oszlopában vannak felsorolva 68 Hasonló táblázatok szerkeszthetők akkor is, ha a “3” primitív elemből indulunk ki:

i 3i LNKO(i,6) ord(3i) = 6/LNKO(i,6) 0 1 6 1 1 3 1 6 2 2 2 3 3 6 3 2 4 4 2 3 5 5 1 6 (Itt is igaz, hogy 36 = 30= 1, tehát nem kell a táblázatban mind a 0-adik, mind a 6-odik hatványt felsorolni.) A j-ed rendű elemek darabszámai pedig Az elem rendje j A G F(7)-ben létező j-ed rendű elemek φ(j) 1 {1} 1 2 {6} 1 3 {2,4} 2 4 Nincs, me rt 4 n em os ztója 6-nak - 5 Nincs, me rt 5 n em os ztója 6-nak - 6 {3,5} 2 Összesen 6 nemzérus elem pontosan ugyanúgy, mint azt az “5” primitív elemből kiindulva már meghatároztuk. 69 A Galois testek additív struktúrájának vizsgálata némileg bonyolultabb, mint az előbbiekben tárgyalt multiplikatív struktúráé volt. Másrészről azonban lényegében nagyon hasonló a multiplikatív struktúra vizsgálatának módszeréhez. A multiplikatív struktúra vizsgálatakor a GF(q) Galois test nemzérus elemeimeinek sorozatát egy β elem 62 ismételt mod q szorzásával

állítottuk elő. A mod q szorzás volt a test feletti multiplikatív művelet és e szorzás ismételt végrehajtását neveztük a β elem hatványozásának. Pontosabb fogalmazással tulajdonképpen mod q hatványozásról kellett volna beszélni A GF(q) Galois test elemeit tehát végül is egyik primitív eleme hatványaiként lehetett előállítani Mellesleg a T 15 tétel következményeként azt is állítottuk, hogy minden galois testnek van legalább egy nemzérus primitív eleme. Az additív struktúra vizsgálatakor is abból indulunk ki, hogy a véges Galois test valamelyik (itt speciálisan az 1, vagyis a multiplikatív egységelemét) kezdjük összeadogatni és ezt a sorozatos összeadogatást szorzásnak tekintjük. Mivel a GF(q) Galois test feletti additív művelet a mod q összeadás (itt körplusszal jelölve), ezért könnyű belátni, hogy a sorozatos összeadogatások eredményei sem nőhetnek a végtelenségig, hanem a sorozat legnagyobb eleme (azaz q-1) után

a sorozatnak ismétlődnie kell. A mod q szorzástól eltérően azonban a sorozat most nem a multiplikatív egységelemmel (azaz “1”-gyel) hanem az additív egységelemmel (azaz “0”-val) kell, hogy kezdődjön. Ez az alábbiak alapján könnyen belátható Vizsgáljuk meg a következő sorozatot: (0), (1), (1⊕1), (1⊕1⊕1), (1⊕1⊕1⊕1), A ⊕ mod q összeadások tagjainak száma egyre növekszik a sorozatban, de csak addig, amíg a tagok száma el nem éri a modulus, azaz q értékét, mert akkor az öszszeadás eredménye 0 lesz, és onnan ismétlődik az addigi sorozat. Ezért nyilvánvaló, hogy az additív struktúra elemeinek sorozata 0-val kell, hogy kezdődjön Ez a gondolatmenet meg is fordítható. Feledkezzünk el most arról, hogy ismerjük a q modulust és vizsgáljuk az ismétlődő sorozatot, hogy hányadik tagjától ismétlődik. D 27 Definició: A Galois test karakterisztikája 63 Egy GF(q) Galois test karakterisztikája az a legkisebb pozitív

egészszám, amelyre m(1) = 0 62 Amint végül is kiderült egy un. primitív elem 63 A ka rakterisztikát itt egyedi jellemzőként kell érteni. Egyébként pedig leginkább a később tárgyalandó testbővítésekkel kapcsolatban van jelentősége ennek a fogalomnak. A Galois test rendjének ( = order) és a k arakterisztikájának a f ogalmai nem az onosak. E rre a lább, a T 17 tételnél visszatérünk. 70 T 16. tétel: Egy Galois test karakterisztikája mindíg prímszám. A tétel bizonyítása egy ellentmondáson alapul. Tételezzük fel, hogy az első ismétlődő elem k(1) “sorszáma” (=k) nem prímszám, hanem összetett szám, azaz m(1).n(1) = k(1) = 0, ahol mind m mind n pozitív egészszámok és mindegyik különkülön kisebb k-nál Egy szorzat azonban csakis akkor lehet 0 ha legalább az egyik tényezője 0 64. Így vagy m(1)-nek, vagy n(1)-nek kellene 0-nak lennie Ha viszont bármelyikre igaz ez, akkor a sorozat ismétlődése nem a k-adik elemnél

kezdődik, hanem egy k-nál kisebb m-edik, vagy n-edik elemnél, ami ellentmond a 27. definiciónak, azaz annak, hogy egy Galois test karakterisztikája az a minimális egészszám stb. Ezzel bizonyítottuk, hogy a Galois test karakterisztikája nem lehet összetett szám. Legyen GF(q) egy p karakterisztikájú Galois test. Ekkor GF(p) összesen p darab különböző elemet tartalmaz. Írjuk fel ezeket az elemeket egy Zp halmazként: Zp = {0, 1, 2(1), 3(1), ,[p-1](1)} A Galois testek speciális tulajdonságairól mindeddig elmondottak miatt Zp a GF(q) Galois test feletti mindkét műveletre nézve zárt. 65 A j(1) ∈ Zp elem additív inverze nyilvánvalóan [p - j](1) ∈ Zp. A j(1) ∈ Zp elem multiplikatív inverze csak akkor értelmezhető, ha j ≠ 0, és j nem egészszámú többszöröse p-nek sem. E feltételek mellet j(1) multiplikatív inverze k(1), ahol j.k ≡ 1 mod p Az algebrai test fogalmára előírt egyéb feltételek (mint az asszociativitás, a disztributivitás,

stb.) már csak azért is teljesülnek, mert Zp bele van ágyazva a GF(q) testbe Így Zp egy p-rendű 66 Galois test és részteste valamennyi p karakterisztikájú GF(q)nak. Már az 5 fejezet bevezető mondataiban állítottuk, hogy a Galois testet egyértelműen meghatározza a rendje 67 Így a GF(p) is egyetlen test és ezért Zp nem más, mint a modulo p összeadás és a modulo p szorzás alatti egészszámok teste. Következésképp egy p karakterisztikájú GF(q) test esetén minden α ∈ GF(q)-ra igaz, hogy p(α) = 0 mert p(α) = p(α.1) = α p(1) = α0 = 0 64 A precizitás kedvéért itt azt is ki kell mondanunk, hogy a m ultiplikatív struktúrában nem lehet zérus elem vagy más szóval a multiplikatív struktúrában nem lehet zérus osztó. (Ti az lenne a zérus elem inverze, márpedig definició szerint kell, hogy létezzen minden elem inverze) 65 Az additív művelet mint láttuk az 1-esek ismételt összeadogatását végzi el, a m ultiplikatív művelet pedig

szintén felfogható az 1-esek i smételt ös szeadogatásából s zármazó t agok szorzataként. 66 Figyeljük meg, hogy itt már a Galois test rendjéről, és nem az imént bevezetett karakterisztikájáról van szó. (Történetesen a Galois testeknél ez a két jellemző számszerűen azonos) 67 Egészen po ntosan: a G F(p) és a G F(q) G alois t estek i zomorfak ha p= q. A z i zomorfizmus a GF(p) vagy a GF(q) elemeinek átnevezéséig igaz. 71 T 17. tétel: Egy q rendű GF(q) Galois test rendje egy prímszám egész hatványa kell, hogy legyen. E tétel bizonyítása abból a gondolatmenetből indul ki, amelyet a T 16. tételnél is követtünk. Ott megmutattuk, hogy minden véges GF(q) test tartalmaz legalább egy darab prímszám-rendű GF(p) résztestet. 68 Ha GF(q) egy additív csoport (márpedig a Galois test additív struktúrájának a vizsgálatából éppen ez derült ki), akkor akár vektortérnek is tekinthető és ebben az esetben a GF(p) résztest feletti

vektortérről van szó. Nem kívánjuk itt az egész bizonyítást végigkövetni, csak utalunk arra, hogy egy GF(q) vektortér vektorait elő lehet állítani az α1β1 + α2β2 + α3β3 + + αmβm alakban, ahol αi ∈ GF(p) és βj ∈ GF(q) (kivéve a j = 0 esetet) 69 Mivel valamennyi α1β1 + α2β2 + α3β3 + + αmβm alakú GF(q) beli elem különböző 70, ezért GF(q) kardinalitása annyi, ahány különböző kombinációja van az ‹α1, α2, α3, , αm,› skalár sorozatnak. Ez pedig éppen pm Lévén p prímszám, ezért GF(q) kardinalitása (és Galois testről lévén szó a rendje is) csakis egy prímszám egész hatványa lehet. 68 Itt és a következőkben is a „p” prímszámot jelent. 69 A vektorterekkel való analógia majdnem teljes. Az αi ∈ GF(p) elemek skalárok itt is, mint a vektortereknél voltak. A különbség csak annyi, hogy itt a báz isvektorok helyett a βj ∈ GF(q) skalárok szerepelnek, de a korábban emlegetett izomorfia miatt ez nem

lényegi különbség. 70 ez az, aminek az bizonyítását az egyszerűsítés kedvéért kihagyjuk ebből a gondolatmenetből 72 6 Primitív polinomok és pm rendű Galois testek. Az előbbiekben megmutattuk, hogy a GF(q) Galois testet egy α ∈ GF(q) primitív elem egymást követő hatványaival (is) elő lehet állítani, ha a hatványkitevők rendre 0, 1, 2, ,(q-1). Egy nemprímszám-rendű 71 Galois testben a szorzást mindíg fel lehet írni úgy, hogy egy szorzat két tényezőjét az α primitív elem hatványaival (mondjuk αi –nel és αj – nel ) írjuk fel és a két hatványkitevőt a szorzáskor modulo (q-1) összeadjuk. A szorzat tehát αi . αj = αi ⊕ j ahol a ⊕ műveleti jel a mod (q-1) összeadást jelenti. P 30. Példa: Galois test elemeinek szorzása a kitevők mod (q-1) összeadásával A P 29. példában vizsgált GF(7)-nek két primitív eleme volt (Ld a 66 oldalon), nevezetesen 3 és 5. Ezek hatványaival elő tudtuk állítani GF(7)

valamennyi elemét a mod 7 szorzás művelete szerint. 3 hatványai a következők voltak: 31 = 3; 32 = 2; 33 = 6; 34 = 4; 35 = 5; 36 = 1; Képezzük az alábbi elempárok szorzatait! a. 2 ⊙ 6 (mod 7) = 3 ⊙ 33 = 32⊕3 = 35 = 5; 2 másképpen számolva: 2 ⊙ 6 (mod 7) = 12 (mod 7) = 5 4 5 4⊕5 b. 4 ⊙ 5 (mod 7) = 3 ⊙ 3 = 3 = 39 mod 6 = 33 = 6; másképpen számolva: 4 ⊙ 5 (mod 7) = 20 (mod 7) = 6 71 Az előző fejezet végén a T 17. tétel csak azt mondta ki, hogy egy GF(q) Galois test rendjének egy p prímszám egész hatványának kell lennie, de ez nem jelenti azt, hogy GF(q) rendjének általában prímszámnak kellene lennie. A kitevők modulo összeadásával történő szorzás itt ismertetett szabálya egyébként prímszám-rendű Galois testekre is érvényes. 73 A Galois test additív struktúrájának a vizsgálata során megmutattuk, hogy bármely GF(q) mindíg tartalmaz egy p prímszám-rendű résztestet, amelynek additív művelete a modulo p

egész összeadás. Ebben a fejezetben a primitív elemek definicióját és szerepét úgy terjesztjük ki, hogy segítségükkel az egész Galois test additív struktúrája kifejezhető legyen. Ehhez olyan polinomokat használunk, amelyek együtthatóit prímszám rendű Galois testekből vesszük. Általános esetben a polinomokban előforduló, együtthatók egy {αi} halmaz elemei 72 Egy tetszőleges (n) fokszámú ilyen polinom általános alakja a következő: α0 + α1 x + α2 x2 +. αn xn egy másik, ugyancsak n fokszámú polinomé pedig β0 + β1 x + β2 x2 +. βn xn E két (azonos fokszámú) polinomon bemutatva az additív és a multiplikatív műveleteket, azok a következők: A két polinom összege: (α0 + α1 x + α2 x2 +. αn xn) + (β0 + β1 x + β2 x2 + βn xn) = = (α0 ⊕ β0) + (α1 ⊕ β1)x + (α2 ⊕ β2)x2 +. + (αn ⊕ βn)xn Figyeljünk arra, hogy (eddig) kétféle összeadás szerepel. Az egyik az a mod p egész öszeadás, amit itt a körplusz

(⊕) műveleti jel ábrázol és az együtthatók skalárhalmaza felett van értelmezve. Ha ezt az algenrai modellt a bináris kódokra alkalmazzuk (mint tenni fogjuk), akkor ez a körplusz művelet a mod 2 összeadást jelenti és az együtthatók a {0, 1} halmaz elemei. A másik „síma” összeadási műveletjel ( + ) a polinom különböző fokszámú tagjait kapcsolja össze. Lényegében ugyanolyan szerepe van, mint a vektortereknél a vektorok komponensei közötti összeadási jelnek. Látni fogjuk alább, hogy az itt éppen bevezetett polinomalgebrai modell a vektorterekkel modellezhető bináris csoportkódok egy speciális alosztályának, nevezetesen a ciklikus kódoknak az modellezésére nagyon jól használható. Ilyen értelemben az n-ed fokú polinom különböző fokszámú komponensei(nek együtthatói) egy n bites (bináris) kód egy-egy bitjének felelnek meg. 72 A bi náris ( ciklikus bl okk) kódokkal k apcsolatos al kalmazásoknál az i tt em lített egy

ütthatók mindíg a {0, 1} halmaz elemei, amely halmaz felett a mod 2 összeadás művelete van értelmezve. 74 P 31. Példa: A {0,1} skalártest feletti n-ed fokú polinom mod n szorzása x-szel Mit jelent egy ilyen polinom x-szel való szorzása? (α0 + α1 x + α2 x2 +. +αn-1 xn-1 +αn xn) ⊙ x1 = = α0x + α1 x1⊞1 + α2 x2⊞1 +. + αn-1 xn-1⊞1 + αn xn⊞1= = α0x + α1 x + α2 x +. + αn-1 x + αn x 2 3 n 0 Amint a P 30. példában felidéztük, a szorzás a kitevők mod (q-1) összeadására vezethető vissza. n-ed fokú polinomok esetén q = n+1 (mert a 0-ad fokú tag miatt éppen ennyi tagja van a polinomnak), tehát a polinom tagjainak kitevőihez (mod n) hozzá kell adni a szorzó kitevőjét. A fenti képletben n-ed fokú polinomról van szó, tehát a kitevők összedásakor alkalmazott mod (n) összeadási művelet (⊞) nem ugyanaz a mod (p) összeadási művelet (⊕), amit az együtthatók összeadásakor alkalmaztunk. Ezért használtunk rá itt

külön műveleti jelet ( t.i a négyzetplusz jelet) Mivel x0 = 1, ezért az előbbi szorzást a tagok kitevőinek növekvő sorrendjébe rendezve a következő eredményt kapjuk: (α0 + α1 x + α2 x2 +. αn xn) ⊙ x = αn + α0x + α1 x2+ α2 x3+ αn-1xn Ha csak az együtthatók sorozatát írjuk le akkor az x-szel való szorzás az ≪α0, α1, α2, , αn≫ együttható-sorozatot áttranszformálja az ≪αn, α0, α1, α2, , αn-1≫ sorozatba, azaz az αi skalárokat mind 1-1 pozicióval jobbra lépteti, a legmagasabb hatvány együtthatóját pedig jobbra “kiléptetve” a sorozatból, “visszacsatolja” a sorozat elejére. A polinom x-szel való szorzása tehát technikailag nagyon egyszerűen megvalósítható egy visszacsatolt léptetőregiszterrel. Polinomot polinommal szorozva a szorzat (mint várható is) a következő: (α0 + α1 x + α2 x2 +. αn xn) ⊙ (β0 + β1 x + β2 x2 + βm xm) = = (α0 . β0) + (α0 β1 ⊕ α1 β0)x + (α0 β2 ⊕ α1 β1⊕

α2 β0) x2 + .+ αn βm) xn+m 75 P 32. Példa: A {0,1} skalártest feletti polinomok összeadása és szorzása Legyenek két polinom együtthatói a GF(2) test elemei, s így az együtthatókra vonatkozó additív művelet a mod 2 összeadás. legyen a példaként választott két polinom a következő: (x5 + x3); és (x3 + x2 + 1); Összegük: (x5 + x3) + (x3 + x2 + 1) = x5 + 2x3 + x2 + 1 = x5 + x2 + 1 3 3 3 mert x ⊕ x = (1 ⊕ 1) x = 0 A szorzatuk: (x5 + x3).(x3 + x2 + 1) = x8 + x7 + x5 + x6 + x5 + x3 = x8 + x7 + x6 + x3 Figyeljük meg, hogy az azonos fokszámú tagok együtthatóinak additív művelete a ⊕ modulo 2 összeadás, általános esetben pedig a skalártest feletti modulo p összeadás. A polinomok szorzása nem gond. Nagyobb probléma egy szorzat-polinom tényezőinek a visszakeresése, más szóval egy polinom faktorizációja Erre mindjárt visszatérünk az irreducibilis polinomok kapcsán A polinomalgebrai modellek általános jelölése A GF(q)[x]

jelölést használjuk arra, hogy az összes, “n” fokszámú (“n” egyébként tetszőleges lehet) α0 + α1 x + α2 x2 +. αn xn olyan polinom “gyűjteményét” jelölje, amely polinomok együtthatói mind az {αi} halmaz elemei. A GF(q) véges test Az ilyen polinomok “gyűjteménye” egy egységelemes kommutatív gyűrűt alkot, amit polinomgyűrűnek is szokás nevezni 76 D 28. Definició: Az irreducibilis polinomok Egy GF(q) beli f(x) polinomot akkor mondunk irreducibilisnak 73, ha f(x) nem bontható GF(q)[x]-beli, f(x)-nél alacsonyabb fokú polinomok szorzatára. P 33. Példa: Polinomok irreducibilitása Az x2 + x + 1 polinom irreducibilis GF(2)[x]-ben, de nem irreducibilis GF(3)[x]-ben. Azt könnyű megmutatni, hogy nincs két olyan elsőfokú polinom, amelyek szorzata GF(2)[x]-ben éppen az x2 + x + 1 polinomot adná, mert az utolsó, 0-ad fokú tag miatt mindkét ilyen elsőfokú polinomban kellene, hogy legyen 0-ad fokú tag, a másodfokú tag miatt

pedig mindkét faktor-polinomban kell, hogy legyen egyegy elsőfokú tag. Azaz összesen kétféle polinom szorzata lenne elképzelhető Ezek a következők: (x + 1).(x + 1) = x2 + 2x + 1, de a mod 2 összeadás érvényes és ezért az elsőfokú tag eredő együtthatója 0. Így az (x + 1)2 = x2 + 1 (mod2) A “másik” szorzat: (x + 1).(x – 1) = x2 – 1 = x2 + 1 (mod2) ugyanaz, mint az előző. Egyik kéttényezős szorzat sem adja tehát ki az eredeti x2 + x + 1 polinomot a GF(2)[x]-ben. Így az x2 + x + 1 polinom GF(2)[x]-ben irreducibilis polinom Más a helyzet GF(3)-ban, ahol az azonos fokú tagok együtthatói a {0, 1, 2} halmazból valók és összeadásukra a (mod 3) additív művelet érvényes. A GF(3)-ban a következők a művelettáblák: 73 ⊕ 0 1 2 ⊙ 0 1 2 0 0 1 2 0 0 0 0 1 1 2 0 1 0 1 2 2 2 0 1 2 0 2 1 Magyarul: nem redukálhatónak. A matematikai terminológia azonban a m agyar szakirodalomban is használja az irreducibilis polinom megnevezést

Ez annak a hagyománynak az alkalmazása, hogy a latin (és a görög) eredetű szakszavakat akkor is alkalmazzák a hazai szakmai nyelvek, ha azokat tulajdonképpen más (pl. angol) szaknyelvből vették át A kiejtésük azonban a magyar nyelvben használt latin szakkifejezések ejtésmódja s nem azé a nyelvé, ahonnan átvette e szavakat a magyar szaknyelv. Ha egy m agasabb f okszámú pol inom al acsonyabb fokszámú polinomok s zorzatára b ontható, akkor redukálható. Ez a fogalomkör tulajdonképpen analóg az összetett számok prímszám-tényezőkre való bontásával: f aktorizációjával. A z i rreducibilis pol inomok eb ben az analógiában a t örzstényezőknek (prímfaktoroknak) felelnek meg. 77 Keressünk két, olyan elsőfokú polinomot, amelyek szorzata a GF(3)-ban éppen x2 + x + 1. Próbálkozzunk a (2x + α).(2x + β) polinomok szorzatával, ahol α és β egyelőre nem ismertek, de azt azonnal láthatjuk, hogy a szorzat másodfokú tagja 4x2 lesz, ami a

modulo 3 algebrában éppen x2-nek felel meg. így a felvett két tényező-polinom mod 3 szorzata: x2 + 2⊙ ( α⊕ β) ⊙x + α⊙ β Ha ezt összevetjük az eredményül kapni kívánt x2 + x + 1 polinommal, akkor az kell, hogy 2⊙(α⊕ β)=1 legyen és α⊙ β =1 legyen (a mod 3 műveletekre nézve). Az imént felírt művelettáblák szerint az α⊙β =1 eredmény csakis úgy jöhet ki, hogy α = β = 1 vagy úgy, hogy α = β = 2 A 2⊙(α⊕β)=1 feltételt az α= β feltétellel összevetve 2⊙2⊙α = 1 (mod 3). Másrészt (α⊕β)=2⊙α = 1 kell, hogy legyen. A multiplikatív (⊙) művelet táblájával összevetve ez mind α = 1 mind α = 2 esetén teljesül, tehát a keresett faktorizáció vagy (2x + 1)2 vagy (2x + 2)2. Próbáljuk ki! A GF(3)-ban (2x + 1)2 = 4x2 + 4x + 1 = x2 + x + 1 (mod3) A másik prímfaktor négyzetével számolva: A GF(3)-ban (2x + 2)2 = 4x2 + 4x + 4 = 4(x2 + x + 1) = 1.(x2 + x + 1) (mod3) Tehát az x2 + x + 1 polinom a GF(3)-ban

faktorizálható, vagyis nem irreducibilis. 74 Az Olvasó az előbbi gondolatmenetet követve bizonyíthatja, hogy az adott x2 + x + 1 polinom a GF(4)-ben irreducibilis. Fontos tanulsága ennek a példának, hogy egy adott polinom lehet irreducibilis valamely GF(q) polinomgyűrűben, de ugyanez a polinom reducibilis (=faktorizálható) egy másik GF(q’) polinomgyűrűben, ha q ≠ q’ Valójában minden polinomhoz található olyan polinomgyűrű, amelyben az adott polinom reducibilis. Így az “irreducibilis polinom” megnevezés mindíg csak valamely meghatározott polinomgyűrűre vonatkoztatva érvényes. 74 Itt már megszűnik az összetett számok tözstényezőkre való bontásával való analógia. Az adott x2+x+1 p olinom ugy anis v agy a ( 2x+1) pol inom négyzeteként, v agy a ( 2x+2) pol inom négyzeteként állítható elő GF(3)[x]-ben, de (2x+1) és (2x+2) szorzataként nem. Erre alább, a primitív polinomok kapcsán visszatérünk. 78 D 29. Definició: A

primitív polinomok Egy m-ed fokú p(x) ∈ GF(p)[x] polinomot akkor mondunk primitív polinomnak ha a legkisebb pozitív n egészszám, amelyre p(x) osztja (xn – 1)-et, nos ez a legkisebb pozitív egész n = pm – 1 Megmutatható, hogy bármely irreducibilis m-ed fokú f(x) ∈ GF(p)[x] polinomra igaz, hogy maradék nélkül osztja xp m −1 -et . P 34. Példák primitív polinomokra Az x2 + x + 1 polinom irreducibilis GF(2)[x]-ben, de nem irreducibilis GF(3)[x]-ben. 79 Szakirodalom. A számítástudomány matematikai alapjainak oroszlánrészét kitevő stúdiumokat már legalább évtizedekkel ezelőtt sokan és sok könyvben, jegyzetben megírták. Valószínűleg pontosabban és matematikai szempontból precízebben is, mint azt ebben az összefoglaló anyagban megtettük. Fel is merült –és joggal merült fel-, hogy miért van szükség egyáltalán ennek az anyagnak az írásbeli összefoglalására. Nos,több szempont is indokolta ezt a vállalkozást Először

is az, hogy az absztrakt algebra, diszkrét matematika, a számítástudomány matematikai alapjai, modern matematika és hasonló címek alatt megírt anyagok vagy matematikusoknak készültek a szó legjobb értelmében vett matematikai precizitással és igényességgel, vagy e matematikai modellek alkalmazóinak az anyagok megírása idején legfelső szintű alkalmazási példákkal, amelyek (mármint az alkalmazási példák) jó része a megírás óta elavult, a gyakorlat meghaladta. Nyilván ez lesz a sorsa ennek az anyagnak is. Mégis indokoltnak látszott egy a főiskolai mérnök hallgatók és informatikusok által megtanulható anyag megírása, különös tekintettel a nemrég bevezetett távoktatásra. Lényeges szempont volt az anyag megírásakor az is, hogy csakis a BMF informatikai és számítógéptudományi stúdiumaiban alapul szolgáló matematikai hátteret tárgyalja és csakis a szükséges (és vélhetően elégséges) mélységben. A következőkben

megadott szakirodalom javarésze nem a fenti indíttatásból készült, de módot adnak az érdeklődőnek arra, hogy egy matematikus precizitási igényességével elmélyüljenek a számítástudomány matematikai modelljeiben és hozzáférjenek azokhoz a bizonyításokhoz is, amelyeket ez az írás többnyire mellőzött. 75 Az író több évtizedes oktatási tapasztalatai alapján úgy véli, hogy a matematikusi és a mérnöki megközelítés elsősorban szemléletében, és ebből következően, módszereiben különbözik. [1] Demetrovics-Denev-Pavlov: A számítástudomány matematikai alapjai. Negyedik kiadás. Nemzeti Tankönyvkiadó, Budapest 19xx ISBN: 963 18 1544 7 (?) [2] Gyögy Anna – Bagyinszki János: [3] György Anna: Diszkrét matematikai példatár 1. és 2 rész A Kandó Kálmán Műszaki Főiskola Matematika és Számítástechnika Intézete Budapest, 1999. KKMF-1177/1-2 [4] Dr. Szendrei János: Algebra és számelmélet Második kiadás.

Tankönyvkiadó 1978 ISBN: 963 17 3137 5 [5] Bagyinszki János-György Anna: Diszkrét matematika főiskolásoknak. Typotex Kiadó, Budapest 2001. ISBN963 9132 96 9 75 A t ipikus m érnöki m egközelítés i nkább „ elhiszi” a m atematikai m odellek t ételeit és a t ételek következményeit és i gyekszik az okat az al kalmazásokhoz k ötni, m intsem „ utánamenne” e tételek bizonyításainak. 80 [6] Stephen B. Wicker: Error Control Systems for Digital Communication and Storage Prentice-Hall Inc. 1995 ISBN: 0-13-200809-2 81