Episode I
Alice és Bob
18. fejezet
Alice és Bob felcsavarja a számegyenest
Az előző fejezet a legnagyobb közös osztó fogalmát általánosítva megismerkedtünk a kitüntetett közös osztóval. Megmutattuk, hogy amennyiben bármely két elemnek létezik a kitüntetett közös osztója egy integritástartományban, úgy az elemek prímtényezős felbontásai – ha egyáltalán léteznek – egyértelműek lesznek. A kitüntetett közös osztó kiszámításához ismertettük az euklidészi algoritmus alapgondolatát a pozitív egész számokon. Ezt az euklidészi függvény fogalmának bevezetésével sikerült működésre bírni egyéb integritástartomány is. Ezeket euklidészi gyűrűknek neveztük. Igazoltuk azt is, hogy a prímtényezős felbontás egyértelműségén túl annak létezése is biztosított ezekben a speciális gyűrűkben. Végül igazoltuk, hogy az egész számok gyűrűje szintén euklidészi gyűrű, és így valóban teljesül benne a számelmélet alaptétele.
De vajon hogyan lehet "felcsavarni" a számegyenest úgy, hogy az alkalmas legyen kriptográfiai kódoló és dekódoló függvények képzéséhez? Mit jelent a "kongruencia" fogalma, és hogyan lehet ezt általánosítani az úgynevezett "ideálok" és "gyűrűhomomorfizmusok" segítségével? Mik azok a "maradékosztálygyűrűk" és hogyan kell bennük számolni? Ebben a fejezetben erről lesz szó...
Figyelem! Ez a fejezet erőteljesen épít a 13. és a 14. fejezetben felépített alábbi definíciókra, valamint a hozzájuk kapcsolódó tételekre:
Ezek kontextusba helyezése miatt erőteljesen ajánlott elolvasni a a 13. és a 14. fejezetet, mivel gyakran hivatkozni fogunk rájuk. Ezenkívül érdemes átismételni a Diffie-Hellman kulcscsere protokollról szóló 9. fejezetet is, ugyanis az ott felületesen már érintett moduláris aritmetika matematikai hátterét fogjuk ebben a fejezetben tárgyalni.
A Diffie-Hellman kulcscsere protokoll kapcsán a 9. fejezetben már szóba kerültek az úgynevezett "egyirányú függvények". Ezek olyan függvények, amelyek esetén a bemenetből algoritmikusan könnyű kiszámítani a kimenetet. Ezzel szemben ha csak a kimenet ismert, abból borzasztóan nehéz kitalálni, hogy mi lehetett a bemenet. Kriptográfiai szempontból az ilyen tulajdonságú függvények azért hasznosak Alice és Bob számára, mert ezek segítségével könnyen közölhetnek egymással olyan információt a nembiztonságos csatornán keresztül, ami a gonosz Eve számára rejtve marad. Eve csak valamilyen egyéb titkos információ birtokában tudná ezeket a függvényeket hatékonyan megfordítani. A számelméleti összefüggések azonban lehetővé teszik, hogy Alice-nak és Bob-nak ezt a – támadó számára létfontosságú – titkot egyáltalán ne kelljen közölniük.
A Diffie-Hellman kulcscsere protokoll során például Alice és Bob egy közös titkos kulcsban való megegyezéshez használt ilyen függvényeket. Ezenkívül az úgynevezett RSA-eljárás is hasonló függvényeket használ. Ez utóbbiról a 21. fejezetben lesz szó részletesen, miután az ehhez szükséges számelméleti fogalmakkal megismerkedtünk. Mindkét eljárás az úgynevezett "moduláris hatványozáson" alapul. A hagyományos hatványozás a már jól ismert szorzásra vezethető vissza. Így például az kifejezést egy olyan szorzatként kell értelmezni, amelynek darab tényezője van, és minden tényezője . Azaz:
A moduláris hatványozást ugyanígy egy tényezős szorzatként értelmezzük. A különbség pusztán annyi, hogy a szorzást ilyenkor nem a hagyományos módon, a mindkét irányban végtelen számegyenesen kell elvégezni, hanem egy véges sok számot tartalmazó "óralapon". A 9.3. szakaszban erről részletesen szó volt, ám az ott szereplő példát vizsgáljuk meg mégegyszer, de mostmár az előző fejezetben az euklidészi algoritmus kapcsán tanult maradékos osztás ismeretében.
Az említett példában a szorzatot kellett kiszámítani a elemet tartalmazó óralapon számolva. Ezt a szorzást úgy végeztük el, hogy először végrehajtottuk a hagyományos szorzást, amiből megkaptuk, hogy összesen lépést kell megtenni az óralapon. Ezután a -ból kiindulva az óramutató járásával megegyező irányban megtettük a lépést. A végeredmény az a szám lett, ahová megérkeztük, azaz . Ez látható a 18.1. ábrán.
Vegyük észre, hogy itt tulajdonképpen egy maradékos osztásról van szó. Ha ugyanis a elemű óralapon lépkedünk, akkor a lépegetés során a egész számú többszöröseinél újra és újra visszajutunk a kiindulópontra. Így azt kell csak meghatározni, hogy az összlépésszám – jelen esetben – mennyi maradékot ad -gyel osztva. A végeredmény a keresett maradék lesz. Jelen esetben a és a közötti maradékos osztást elvégezve ez adódik:
A kapott hányados azt adja meg, hogy a lépegetés során összesen hányszor fogunk visszajutni a kezdőpontba. A maradékból pedig megkapjuk, hogy ezen felül még hány lépést kell pluszban megtennünk. A végeredmény szempontjából az óraaritmetikában csak a maradék fontos, a kapott hányados elfelejthetjük.
18.1Számolás maradékokkal
A moduláris hatványozás alapja tehát az iménti példában látott moduláris szorzás. Problémát jelenthet azonban, ha a kitevő túl nagy. Például a hatvány óraaritmetikában való kiszámításához nem lenne szerencsés, ha előbb ki kellene számítanunk a
szorzatot, amelynek tényezője van. Ilyenkor ugyanis még a maradékképzés előtt egy olyan nagy számot kapnánk részeredményként, amelynek hatására a számítógépünk tárolóregisztereiben úgynevezett "túlcsordulás" következne be.
A 3. fejezetben a digitális áramkörökben történő számábrázolás kapcsán már volt szó arról, hogy a számítógépek általában maximum 64 bináris számjegyen tárolják a számokat. Mármost a részeredmény egészen pontosan bináris számjegyen férne el. A számítógép ezt a problémát úgy "oldja meg", hogy jobb esetben elhasal programhibával, rosszabb esetben pedig az első darab bináris számjegyet levágja a részeredmény elejéről, és az így kapott hibás részeredménnyel számol tovább. El lehet képzelni, hogy ennek milyen beláthatatlan következményei lennének.
Ahhoz, hogy ezt a problémát megoldjuk, előszöris igazolni fogjuk az egész számok közötti maradékos osztás egy fontos tulajdonságát. A 17.17. Definícióban a maradékos osztás során képződő maradékokra csak annyit kötöttünk ki, hogy az euklidészi függvény szerinti "értékük" legyen kisebb, mint az osztó ugyanilyen értelemben vett "értéke". Ebből általában még nem következik, hogy a maradék egyértelmű lesz.
Például az és egész számok között kétféleképpen is elvégezhetjük a maradékos osztást:
Első esetben , második esetben pedig lesz a maradék. Mindkettő helyes, hiszen a gyűrűben az abszolútérték-függvényt használjuk euklidészi függvényként. Márpedig mindkét maradéknak kisebb az abszolút értéke, mint az osztónak, ami ugye jelen esetben . Azt fogjuk megmutatni, hogy amennyiben a maradékra még azt is kikötjük, hogy nemnegatív, úgy a maradékos osztás továbbra is elvégezhető, ám ebben az esetben már csak egyféleképpen.
Ehhez először szükségünk lesz egy egyszerű segédtételre, amely a továbbiakban is hasznunkra lesz.
Mostmár igazolhatjuk, hogy az egész számok közötti nemnegatív maradékos osztás egyértelmű.
Ez azért jó hír a számunkra, mivel így minden egész számhoz hozzá tudunk rendelni egy nemnegatív maradékot, amelyet -nak egy valamilyen egész számmal végzett maradékos osztása eredményezne. Ez a hozzárendelés ugye az iménti tétel értelmében egyértelmű lesz, azaz minden egész számhoz pontosan egy maradékot rendel. Így tulajdonképpen egy függvényt kapunk. Ennek a függvénynek az értékkészlete ráadásul véges lesz, hiszen pontosan darab olyan nemnegatív egész szám létezik, amely maradékként szóba jöhet, azaz értéke kisebb, mint abszolút értéke. Például vagy esetén ezek a , az és a nemnegatív egész számok.
Ezek az osztási maradékok tehát egy véges halmazt alkotnak. Ennek elemei között két műveletet is tudunk értelmezni az imént említett függvény segítségével. Erről szól az alábbi definíció, valamint az alatta szereplő megjegyzések és példák.
Nézzünk is egy egyszerű példát a fenti definícióban foglaltakra. Legyen például . Ekkor ugye a halmazról van szó, amelynek mindössze a , az és a lesznek az elemei. Az alábbiakban a függvény néhány hozzárendelését tüntettük fel:
Az alábbi két táblázatban pedig a halmazon értelmezett és műveletek úgynevezett "műveleti táblái" láthatók:
Például a moduláris összeadás eredményét a második sor első oszlopából tudjuk kiolvasni a baloldali táblázatból, ami ugye . A műveletet a fenti definíció szerint elvégezve valóban -t kapunk, hiszen
Az eredménye ehhez hasonlóan az első sor második oszlopában szerepel, ami – hatalmas meglepetésre – szintén . A moduláris szorzás táblázata ugyanígy értelmezendő. Például . Nyilván, hiszen ha -t elosztjuk -mal, akkor épp lesz a maradék.
Hamarosan visszatérhetünk a szakasz elején felvetett hatványozással kapcsolatos problémára. Előbb azonban megmutatjuk, hogy a moduláris összeadás és szorzás pontosan ugyanazokkal a "jól megszokott" tulajdonságokkal rendelkezik, mint a szokásos összeadás és szorzás.
18.2Egyenletek megoldása a gyűrűben
Eszerint tehát amikor modulo maradékokkal számolunk, akkor nyugodtan hagyatkozhatunk minden olyan eddigi tételre, amelyeket eddig kommutatív gyűrűkre bizonyítottunk. Nagyjából minden ugyanúgy fog működni, ahogyan azt az egész számok esetén már megszoktuk.
De csak nagyjából! Az egyenletek megoldásánál a 18.4. Tétel szerinti gyűrűben körültekintően kell eljárnunk. A természetes számok körében a 14.1. szakaszban felhoztunk egy egyszerű példát. Akkor a egyenletet kellett megoldanunk a ezen a számhalmazon. A problémát az okozta, hogy "kivonás" és "osztás" ebben a számkörben, mint algebrai értelemben vett "művelet" nem állt rendelkezésünkre. Ezért az alábbi két segédtételt voltunk kénytelenek felhasználni "kivonás" és "osztás" helyett:
Most térjünk vissza a szóbanforgó egyenletünkhöz. Első lépésként az egyenlet jobboldalát helyett egy kéttagú összegként írtuk fel:
Ebből a 12.18. Lemma alapján következik.
Ezután második lépésként ennek jobboldalát helyett egy kéttényezős szorzatként írtuk fel:
Ebből viszont a 14.2. Lemma alapján az megoldás következik.
Azaz a természetes számok körében egy egyenlet megoldásakor mindkét oldalból büntetlenül szabad volt "kivonni" ugyanazt a tetszőleges számot, valamint mindkét oldalt szabad volt "elosztani" ugyanazzal a tetszőleges nemnulla számmal. Méghozzá annak ellenére, hogy ez a két "művelet" ezen a számhalmazon nem állt rendelkezésünkre. Megemlítettük ugyanakkor – épp erre a szakaszra hivatkozva –, hogy más algebrai struktúrákban nagyon könnyen kaphatunk hibás eredményt, ha az ehhez hasonló lépéseket nem kellő körültekintéssel végezzük el.
A fenti két segédtételt azután a 15.1. szakaszban általánosítottuk tetszőleges gyűrűkre is. Itt a kivonással már nincs gond, hiszen az tetszőleges gyűrűben korlátlanul elvégezhető. Osztani azonban általában továbbra sem tudunk, mivel multiplikatív inverz létezése csak testekben garantált, a 15.4. Tétel azonban mégis a segítségünkre sietett. Eszerint a tétel szerint nullosztómentes gyűrűkben, és – ami talán még fontosabb – csak azokban továbbra is lehet tetszőleges nemnulla elemmel "elosztani" egy egyenlet mindkét oldalát. Kérdés, hogy vajon a gyűrű minden esetén nullosztómentes-e?
Térjünk most vissza a fenti egyenletünkhöz, és ismét próbáljuk meg megoldani azt, ám ezúttal keressük a megoldást mondjuk a gyűrűben. A 18.3. Definícióban bevezetett műveleti jelekkel ez az egyenlet az alábbi formát ölti – a könnyebb áttekinthetőség kedvéért a műveleti sorrendet zárójelekkel is kihangsúlyoztuk:
A "kivonás" – mint említettük – gond nélkül elvégezhető. Emlékeztetjük az Olvasót, hogy egy gyűrűben "kivonás" alatt az ellentettel való összeadást értjük. Így tehát most adjuk hozzá az egyenlet mindkét oldalához a ellentettjét. A gyűrűben ez az lesz, hiszen a moduláris összeadás 18.3. Definíciója alapján
A baloldalon tehát marad, míg a jobboldalon -et kapunk, hiszen:
Az egyenletünk tehát most a következő:
Gondolhatnánk, hogy innen már egyszerű a dolgunk, hiszen – hasonlóan a természetes számok körében alkalmazott megoldáshoz – felírhatjuk a jobboldalon szereplő -et egy kéttényezős szorzatként alakban:
Ha azonban most meggondolatlanul alkalmazzuk szépen a 15.4. Tételt, és erre hivatkozva mindkét oldalt "egyszerűsítjük" -vel, akkor könnyen azt a következtetést vonhatjuk le, hogy a fenti egyenletből következik.
Ez azonban hibás érvelés! Az valóban megoldása a
egyenletnek, azonban van még egy további megoldás is. Nevezetesen az , amely fölött ezzel a lépéssel szépen átsiklunk.
Ellenőrizzük csak le, hogy a gyűrűben valóban teljesül az alábbi:
Mi okozhatja hát a problémát? Ha tüzetesen megvizsgáljuk az egyenletek egyszerűsíthetőségéről szóló 15.4. Tételt, akkor feltűnhet, hogy az kizárólag nullosztómentes gyűrűkre érvényes. Márpedig ha -ban ez a lépés nem működik, az csak úgy lehetséges, hogy ez a gyűrű bizony nem nullosztómentes. Ez azonnal látható is, ha megvizsgáljuk a gyűrű "szórzótábláját":
Ha megfigyeljük, ebben a táblázatban az első soron és oszlopon kívül is bőven szerepel a nullelem. Ez azt jelenti, hogy egy szorzat olyan esetekben is lehet , amikor történetesen egyik tényezője sem az. Ilyen például a szorzat, hogy csak egyet említsünk. Jó lenne tehát valami általános szabály arra vonatkozóan, hogy mely esetekben nullosztómentes a gyűrű, és mely esetekben nem. Erről szól az alábbi tétel.
18.3A moduláris hatványozás tulajdonságai
Mostmár visszatérhetünk az eredeti hatványozással kapcsolatos problémánkhoz, és általánosan is megfogalmazhatjuk azt. Eszerint tehát a feladat az, hogy adott és egész számok esetén számítsuk ki azt a maradékot, amelyet az hatvány ad valamilyen egész számmal osztva. A konkrét feladatban a hatvány -gyel való osztási maradékát kellett kiszámítani. A probléma ugye az, hogy ezt az hatvány tényleges kiszámítása nélkül kellene megtennünk, máskülönben a modulo maradékképzés előtt kapott részeredmény kezelhetetlenül nagy lenne.
Azt viszont láttuk a 18.2. szakaszban, hogy a gyűrűben ilyen szempontból sokkal könnyebb számolni, hiszen itt minden részeredmény egy véges számhalmazból kerül ki. Érdemes volna tehát már az elején "áttérni" a gyűrűre, és a hatványozást már az itteni moduláris szorzással végezni. Ehhez azonban az kell, hogy ez az "áttérés" ne befolyásolja a kapott végeredményt. Azaz ha előbb "áttérünk" a gyűrűbe és ott végezzük el a moduláris szorzásokat, akkor ugyanazt kell kapnunk, mintha előbb a gyűrűben végeznénk el a hagyományos szorzásokat, majd vennénk az így kapott eredmény -beli megfelelőjét.
A 13.5. szakaszban a természetes számok -be való beágyazásánál már volt szó az úgynevezett struktúratartó leképezésekről, amelyeket a 13.9. Definícióban homomorfizmusoknak neveztünk. Nekünk most a fentiek alapján épp egy ilyen leképezésre lenne szükségünk a és gyűrűk között. Erről szól az alábbi definíció, amely tehát a homomorfizmusfogalom speciális esete gyűrűkre, mint algebrai struktúrákra. Kivételesen feltüntettük a gyűrű műveleti jeleit is annak érdekében, hogy világos legyen, mikor melyik gyűrűben kell az adott műveletet elvégezni.
18.6. Definíció (Gyűrűhomomorfizmus):
Tegyük fel továbbá, hogy tetszőleges -beli és elemekre teljesülnek az alábbi követelmények:
Ekkor az függvényt gyűrűhomomorfizmusnak nevezzük.
Amennyiben minden eleme legalább egy -beli elemhez hozzá van rendelve által, akkor -et szürjektív gyűrűhomomorfizmusnak (vagy gyűrűráképzésnek) nevezzük. Ez a szituáció látható a 18.2. ábrán.
Amennyiben minden eleme legfeljebb egy -beli elemhez van hozzárendelve által, akkor -et injektív gyűrűhomomorfizmusnak (vagy gyűrűbeágyazásnak) nevezzük. Ez a szituáció látható a 18.3. ábrán.
Amennyiben minden eleme pontosan egy -beli elemhez van hozzárendelve által, akkor -et bijektív gyűrűhomomorfizmusnak (vagy gyűrűizomorfizmusnak) nevezzük. Ez a szituáció látható a 18.4. ábrán.
Ilyenkor azt mondjuk, hogy az és az gyűrű izomorf egymással. Ezt így jelöljük:
Megjegyzés:
A gyűrűizomorfizmusra, mint gyűrűk közötti relációra teljesülnek az alábbi tulajdonságok:
Nyilván, hiszen az leképezés nyilvánvalóan gyűrűizomorfizmus -ből önmagába.
Nyilván, hiszen ha a nyilak irányát megfordítjuk, akkor az így kapott fordított irányú leképezés is kölcsönösen egyértelmű. Ez azt jelenti, hogy ha az gyűrű tetszőleges eleme, akkor létezik olyan elem az gyűrűben, amelyre teljesülnek az alábbiak:
Ekkor azonban művelettartó tulajdonságai, valamint a fentiek miatt teljesülnek az alábbi egyenletek:
A leképezés tehát szintén gyűrűizomorfizmus, csak épp -ből mutat -be.
Jelöljük ugyanis -sel az -ből -be mutató, -vel pedig az -ből -be mutató gyűrűizomorfizmust. Ezek után definiáljuk az -ből közvetlenül -be mutató leképezést és egymás után alkalmazásaként. Azaz tetszőleges -beli elemre legyen
A 18.5. ábrán azonnal látszik, hogy az -ből -be mutató leképezés tulajdonképpen az és leképezéseket reprezentáló nyilak összekapcsolása, amely nyilván kölcsönösen egyértelmű:
Az alábbi tételben meg is adunk egy gyűrűhomomorfizmust az egész számok gyűrűjéből a véges sok elemet tartalmazó gyűrűbe. Nem lesz túl meglepő a dolog, hiszen ez a leképezés mindvégig itt volt az orrunk előtt.
Az iménti tételt alkalmazva mostmár könnyedén kiszámíthatjuk, hogy a hatvány mennyi maradékot ad -gyel osztva. Ehhez annyit kell tennünk, hogy a darab tényezőre alkalmazzuk a maradékképző függvényt, és az így kapott maradékokon elvégezzük a moduláris szorzást a gyűrűben. Mivel az imént bizonyított 18.7. Tétel alapján a függvény egy gyűrűhomomorfizmus és között, ezért igaz lesz az alábbi összefüggés:
Az a probléma tehát megoldódott, hogy a számolgatás közben nem fogunk olyan óriási részeredményeket kapni, amelyek túllépik a számítógép számábrázolási határait. Megjegyezzük ugyanakkor, hogy a gyakorlatban a tényezők számának nagyságrendje a többszázjegyű számok körében mozog. Ez a módszer tehát ebben a formában továbbra sem alkalmazható, mivel beláthatatlanul sok moduláris szorzást igényel. A 21.4. szakaszban azonban mutatni fogunk egy olyan módszert, amelynek a segítségével még ezek a nagyon soktényezős moduláris hatványok is pillanatok alatt kiszámíthatók.
Ez az "ismételt négyzetre emelések módszere" néven ismeretes, és – anélkül, hogy most belemennénk a részletekbe – a moduláris hatványozás azonosságait fogja igen trükkös módon kihasználni. Ezek az azonosságok azonban tetszőleges kommutatív gyűrűben érvényesek, így az alábbi tételben ezt az általános esetet fogjuk igazolni.
18.4A Diffie-Hellman kulcscsere protokoll helyessége
Mivel az imént bizonyított 18.8. Tétel tetszőleges kommutatív gyűrűre érvényes, így érvényes a gyűrűre is. Ez szoros összefüggésben van a 9.5. szakaszban már részletesen ismertetett Diffie-Hellman kulcscsere protokollal. Ennek helyességét akkor nem igazoltuk, így ezt most fogjuk megtenni. Ott ugye gyakorlatilag a gyűrűben kell moduláris hatványozást végezni. Ha Alice és Bob egy titkos kulcsban akarnak megállapodni, akkor először a nembiztonságos csatornán keresztül megállapodnak egy egész számban és egy modulusban, amelyet mindketten majd a moduláris hatványozáshoz fognak használni. Ezután mindketten kitalálnak maguknak egy-egy titkos kitevőt. Tegyük fel, hogy Alice titkos kitevője , Bob-é pedig . Ezeket a kitevőket egymásnak sem árulják el.
Ezután Alice a gyűrűben elvégzi az moduláris hatványozást, és az eredményt átküldi Bobnak. Bob ugyanígy elvégzi az moduláris hatványozást, és az eredményt átküldi Alice-nak. Ezután a kapott számokra mindketten ismét elvégzik a moduláris hatványozást a saját titkos kitevőjükkel. Azaz Alice a Bob-tól kapott számra elvégzi az , Bob pedig az Alice-tól kapott számra elvégzi az moduláris hatványozást.
A 18.8. Tétel 2. pontja alapján azonban mindketten ugyanazt a számot fogják kapni:
A Diffie-Hellman kulcscsere protokoll tehát valóban helyesen működik, mivel a moduláris hatványozás ugyanazokkal a tulajdonságokkal rendelkezik, mint a hagyományos hatványozás, hiszen ezek a tulajdonságok a 18.8. Tétel alapján bármely kommutatív gyűrűben érvényesek. Már csak azt a problémát kell megoldanunk, hogy ezeket a moduláris hatványozásokat óriási kitevők esetén is nagyon hatékonyan el tudjuk végezni. Erre – mint már említettük – a 21.4. szakaszban fogunk kitérni az úgynevezett "ismételt négyzetre emelések módszere" kapcsán, amely szintén a 18.8. Tételben felsorolt tulajdonságokat használja ki.
18.5Kongruenciák
Most azonban ismerkedjünk meg további fontos fogalmakkal a 18.6. Definícióban ismertetett gyűrűhomomorfizmusok kapcsán. Tegyük fel, hogy adva van egy és egy gyűrű, valamint egy közöttük lévő művelettartó leképezés, azaz gyűrűhomomorfizmus. Ez tehát minden eleméhez hozzárendel valamilyen -beli elemet. Elképzelhető azonban, hogy egy adott -beli elem több -beli elemhez is hozzá van rendelve. Így tehát elemei között definiálhatunk egy relációt, amely azt fejezi ki két -beli elem között, hogy nekik ugyanaz az gyűrűhomomorfizmus szerinti képük az gyűrűben. Erről szól az alábbi definíció.
A 13.3. szakaszban már megismerkedtünk az úgynevezett ekvivalenciarelációkkal. Ezek olyan relációk voltak, amelyek egy halmaz elemeit úgynevezett ekvivalencia-osztályokba sorolják. Méghozzá olymódon, hogy az egyes osztályok között nincs átfedés, és minden elem bekerül valamelyik osztályba. Az szerinti kongruencia fenti definíciójából azonnak adódik, hogy ez a reláció szintén egy ekvivalenciareláció.
Ez alapján tehát az gyűrűhomomorfizmus az gyűrűt maradékosztályokra bontja, és egy adott maradékosztályban minden elemnek ugyanaz lesz az szerinti képe az gyűrűben. A 18.6. ábrán például a és gyűrűk között lévő, a 18.3. Definícióban már ismertetett maradékképző függvény – amely ugye a 18.7. Tétel alapján egy gyűrűhomomorfizmus – szerinti maradékosztályokat szemléltetjük.
Az ábra baloldalán az egész számok gyűrűjét reprezentáló, mindkét irányban végtelen számegyenes "felcsavarva" látható. Méghozzá olymódon, hogy az azonos maradékosztályba kerülő egész számok egy vonalba essenek. Ezek épp azok a számok lesznek, amelyek -mal osztva azonos maradékot adnak. Az ábra jobboldalán a gyűrűhomomorfizmus képhalmaza, tehát jelen esetben a halmaz látható. Ennek elemeit egy óralapon helyeztük el ahhoz hasonlóan, ahogyan a 9.3. szakaszban szemléltettük az "óraaritmetikát" a Diffie-Hellman kulcscsere protokoll kapcsán. A két halmaz közötti leképezést nyilakkal szemléltettük, amely tehát minden egész számhoz az ő modulo maradékát rendeli hozzá.
Felmerülhet az Olvasóban a kérdés, hogy a 18.9. Definícióban, valamint a 18.10. Tételben miért kötöttük ki a két gyűrű közötti függvényről, hogy az gyűrűhomomorfizmus legyen. Hiszen a kongruenciát, mint relációt az eddigiek alapján definiálhattuk volna tetszőleges függvény szerint is. Az ugyanúgy egy ekvivalenciareláció lenne, ugyanis a 18.10. Tétel bizonyításában egyáltalán nem használtuk ki az leképezés művelettartó tulajdonságait. Rövidesen világos lesz, hogy miért olyan fontos ez a tulajdonság.
18.6Gyűrűhomomorfizmus magja és képe
Képzeljük el azt a szituációt, hogy adott egy valamilyen gyűrű, valamint egy ezen értelmezett gyűrűhomomorfizmus, de nem ismerjük azt az gyűrűt, amelybe képez. Szeretnénk azonban feltárni szerkezetét. Hamarosan látni fogjuk, hogy ehhez előszöris az szerinti kongruenciareláció által kijelölt -beli maradékosztályokat kell meghatároznunk.
Első körben azt gondolnánk, hogy erre nincs más mód, mint összes elemére alkalmazni az függvényt, és a kapott függvényértékek alapján meghatározni ezeket a maradékosztályokat. Szerencsére van egy ennél sokkal egyszerűbb módszer, ám ehhez már szükségünk lesz összegtartó tulajdonságára. Először ismertetünk egy hasznos segédtételt, amely ezt a tulajdonságot használja ki.
Térjünk most vissza az eredeti problémánkhoz, amikoris egy gyűrűből kiinduló, gyűrűbe mutató valamilyen gyűrűhomomorfizmus szerinti kongruenciareláció maradékosztályait szeretnénk meghatározni. A 18.11. Lemma következményeként most meg fogjuk mutatni, hogy ezek között van egy kitüntetett maradékosztály, amely már egyértelműen meghatározza az összes többit. Ez a kitüntetett maradékosztály épp azokból az -beli elemekből áll, amelyekhez az leképezés az gyűrű nullelemét rendeli hozzá. Ennek a kitüntetett maradékosztálynak, valamint az értékkészletének külön nevet is ad az alábbi definíció.
18.12. Definíció (Gyűrűhomomorfizmus magja és képe):
Legyenek és tetszőleges gyűrűk, valamint legyen adva közöttük egy gyűrűhomomorfizmus. Ekkor az gyűrűhomomorfizmus magjának nevezzük azon -beli elemek halmazát, melyeknek szerinti képe az gyűrű nulleleme. Az magját – az angol "kernel" szóból eredeztetve – így jelöljük:
Az gyűrűhomomorfizmus képének nevezzük azoknak az -beli elemeknek a halmazát, amelyek képei legalább egy -beli elemnek. Az képét – az angol "image" szóból eredeztetve – így jelöljük:
A 18.7. ábra szemlélteti ezeket a fogalmakat.
Például a 18.5. szakaszban felvázolt és közötti maradékképző függvény – mint gyűrűhomomorfizmus – magja épp a -mal osztható egész számokból áll. A függvény ugyanis pontosan ezekhez rendeli hozzá a gyűrű nullelemét, azaz a maradékot. A függvény képe pedig a 18.3. Definíció utáni megjegyzés 5. pontja miatt maga a halmaz.
Megjegyezzük továbbá, hogy egy gyűrűhomomorfizmus magja soha nem lehet üres. A 18.11. Lemma 1. pontja alapján ugyanis szükségképpen tartalmazza legalább az gyűrű nullelemét, hiszen ennek képe biztosan az gyűrű nulleleme lesz.
Most azt mutatjuk meg, hogy egy gyűrűhomomorfizmus magja már egyértelműen meghatározza az általa indukált kongruenciarelációt.
Ez alapján tehát egy gyűrűhomomorfizmus szerinti kongruenciarelációt kizárólag annak magja, nem pedig maga határozza meg. Még csak az sem érdekes, hogy milyen gyűrűbe képez. Nézzünk is erre egy egyszerű példát.
Legyen most a kiindulási gyűrűnk az egész számok gyűrűje, és legyen az egyik célgyűrű a 18.3. Definíció szerinti gyűrű. A másik célgyűrű elsőre szokatlan lesz, mivel ennek alaphalmaza nem számokból, hanem az és az betűkből áll. Ezt a halmazt -vel fogjuk jelölni a példában. Vezessünk be ezen a halmazon is két műveletet, jelöljük őket a és a szimbólumokkal, és definiáljuk őket önkényesen az alábbi műveleti táblákkal:
Könnyű leellenőrizni, hogy a halmaz ezzel a két művelettel szintén gyűrűt alkot, melynek nulleleme az betű, egységeleme pedig az betű. Ennek legegyszerűbb módja, ha meggondoljuk, hogy ez a gyűrű -től pusztán abban különbözik, hogy máshogy jelöltük az elemeit és a két műveletét.
Valóban, az Olvasó is könnyedén leellenőrizheti, hogy az alábbi leképezés tulajdonképpen egy 18.6. Definíció szerinti gyűrűizomorfizmus a és a gyűrűk között, azaz :
A 18.9. szakaszban meg fogjuk mutatni, hogy ez a gyűrűizomorfizmus nem véletlenül teljesül e két gyűrű között, ám egyelőre tegyük félre ezt a dolgot. Van tehát egy kiindulási gyűrűnk, amely az egész számok gyűrűje, valamint van két célgyűrűnk: a és az imént definiált, meglehetősen szokatlan . Nincs más hátra, mint találni két -ből kiinduló gyűrűhomomorfizmust, amelyeknek ugyanaz a magja -ben, azonban az egyiknek a célgyűrűje , a másiknak pedig .
Az első viszonylag egyszerű, hiszen a 18.3. Definíció szerinti maradékképző függvény a 18.7. Tétel alapján egy gyűrűhomomorfizmus és között. Ennek magja a -vel osztható – tehát páros – számokból áll, hiszen pontosan ezek fognak maradékot adni -vel osztva.
A másik gyűrűhomomorfizmust az alábbi függvénnyel adjuk meg:
Az Olvasóra bízzuk annak átgondolását, hogy valóban egy gyűrűhomomorfizmus és között. Mivel az betű a gyűrű nulleleme, ezért az gyűrűhomomorfizmus magja szintén a páros számokból áll.
A három gyűrűt és a közöttük lévő és gyűrűhomomorfizmusokat, illetve ezek közös magját mutatja a 18.8. ábra.
Erre a szituációra már alkalmazhatjuk a kongruenciák ekvivalenciájáról szóló 18.13. Tételt. Eszerint tehát a két gyűrűhomomorfizmus – habár azok teljesen más gyűrűkre képeznek – szerinti kongruenciarelációk teljesen azonosak lesznek. Ez azt jelenti, hogy az alábbi két kongruencia tetszőleges és egész számok között vagy egyszerre teljesül, vagy egyszerre nem teljesül:
Ezt a két kongruenciarelációt tehát teljesen felesleges megkülönböztetni egymástól. Sőt, általában is hasznos lenne bevezetni egy olyan kongruencia-fogalmat, amely nem támaszkodik közvetlenül egy adott konkrét gyűrűhomomorfizmusra, hanem annak csak a magjára. A 18.7. szakaszban pontosan ezt fogjuk megtenni.
18.7Részgyűrűk és ideálok
Tegyük fel, hogy van egy gyűrű, amelyen egy kongruenciarelációt szeretnénk megadni. Nem szeretnénk ugyanakkor foglalkozni semmiféle más gyűrűvel, abba mutató gyűrűhomomorfizmusokkal meg aztán pláne nem. Szerencsére a 18.6. szakaszban bizonyított 18.13. Tétel alapján nekünk elegendő -ben egy olyan részhalmazt keresni, amely alkalmas arra, hogy valamilyen gyűrűhomomorfizmus magja legyen. Ezt azonban ennek a hipotetikus gyűrűhomomorfizmusnak a konkrét ismerete nélkül szeretnénk megtenni. Ehhez először is definiálunk egy, a továbbiakban is hasznos fogalmat.
A 16.1. szakaszban az oszthatóság kapcsán már láttuk, hogy például a páros számok -vel jelölt halmaza maga is gyűrű a -n értelmezett összeadásra és szorzásra nézve, így részgyűrű -ben. Mivel nem minden egész szám páros, ezért , azaz valódi részgyűrű -ben. A páratlan számok szintén részhalmazt alkotnak -n belül, ez a részhalmaz azonban nem részgyűrű, hiszen már a műveleti zártság sem teljesül az összeadásra. Például , ami nem páratlan szám.
Az alábbi tétel abban nyújt segítséget, hogy ne kelljen minden 14.12. Definíció szerinti gyűrűaxiómát ellenőriznünk ahhoz, hogy egy részhalmazról eldöntsük, vajon részgyűrű-e vagy sem.
Még mielőtt visszatérnénk egy adott gyűrűből kiinduló gyűrűhomomorfizmusok magjainak azonosítására, vizsgáljuk meg azt a kérdést, hogy hogyan azonosíthatjuk egy adott gyűrűbe mutató gyűrűhomomorfizmusok képeit. Az alábbi tétel alapján ezekről sajnos nem tudunk túl sokat mondani.
Egy gyűrű esetén tehát az odamutató gyűrűhomomorfizmusok képeiről mindössze annyit tudunk mondani, hogy azok pontosan részgyűrűi lesznek. Ezzel szemben egy gyűrű azon részhalmazairól, amelyek valamilyen, -ből kiinduló gyűrűhomomorfizmusok magjai lehetnek, ennél többet is fogunk tudni mondani. Most erre mutatunk egy szükséges feltételt, majd a 18.8. szakaszban igazoljuk azt az egyáltalán nem nyilvánvaló tényt, hogy ez a feltétel egyben elégséges is.
Bizonyítás:
Tekintsük azt az gyűrűhomomorfizmust, amelynek a magja. Ez egy valamilyen, számunkra ismeretlen gyűrűbe képez, amelynek nullelemét jelöljük most -szel, míg az gyűrű nullelemét jelöljük -rel. Az függvény tehát minden eleméhez -et rendeli hozzá, hiszen . Ezt a szituációt mutatja a 18.9. ábra.
Az 1. tulajdonság igazolásához azt kell megmutatni, hogy részgyűrű -ben. Ez a 18.15. Tétel alapján pontosan akkor teljesül, ha tartalmazza -t, valamint zárt az gyűrű mindkét műveletére és az -beli ellentettképzésre.
Mivel gyűrűhomomorfizmus, ezért nyilván összegtartó is, így a 18.11. Lemma értelmében tartja a nullelemet és az ellentettképzést. Azaz egyrészt , és így valóban benne van magjában, azaz -ben. Másrészt ha valamilyen benne van -ben, akkor , és így az ellentettképzés tartása miatt
Azaz ellentettjének is a képe, következésképp ő is benne van -ben.
Az összeadásra való zártság szintén összegtartó tulajdonságából ered. Ha ugyanis és az két tetszőleges eleme, akkor egyrészt teljesülnek az alábbiak:
Másrészt viszont az összegtartás miatt az ő összegükre teljesül az alábbi:
Tehát az összeg is az gyűrű nullelemére képeződik, következésképp ő is benne van -ben. A szorzásra való zártság teljesen hasonló módon következik szorzástartó tulajdonságából. Mivel teljesül a 18.15. Tétel szerinti összes feltétel, ezért valóban részgyűrű -ben.
A 2. tulajdonság igazolásához tegyük fel, hogy az gyűrű tetszőleges – tehát nem feltétlenül -beli – eleme. Azt kell megmutatni, hogy amennyiben ezzel akár balról, akár jobbról megszorzunk egy -beli elemet, akkor az eredmény is -beli lesz. Mivel benne van -ben, ezért . Következésképp szorzástartó tulajdonsága miatt az és szorzatok képére igazak lesznek az alábbiak:
Elképzelhető ugyan, hogy a két szorzatnak nem ugyanaz lesz az eredménye az gyűrűben – kivéve persze ha kommutatív gyűrűről van szó –, de az biztos, hogy mindkét szorzat szerinti képe az gyűrű nulleleme lesz. Következésképp valóban benne vannak -ben.
A 18.17. Tételben felsorolt két tulajdonságot tehát egy gyűrű minden olyan részhalmaza teljesíti, amely egy valamilyen gyűrűhomomorfizmus magja lehet. Ezeknek a részhalmazoknak külön nevet is ad az alábbi definíció.
Például az egész számok gyűrűjében ideált alkot a páros számok -vel jelölt halmaza, hiszen ha egy páros számot bármilyen tetszőleges egész számmal megszorzunk, az eredmény ugyancsak páros. Ezzel szemben a páratlan számok halmaza nem alkot ideált, hiszen ez a halmaz még csak nem is részgyűrű -ben.
Az iménti definícióban megismert szóhasználattal élve a 18.17. Tétel úgy is megfogalmazható, hogy amennyiben egy gyűrű valamely részhalmaza magja valamilyen gyűrűhomomorfizmusnak, akkor ideál -ben. A 18.8. szakaszban azt fogjuk megmutatni, hogy más részhalmaz nem is lehet gyűrűhomomorfizmus magja.
18.8Maradékosztálygyűrűk
Előszöris bevezetünk egy új jelölésmódot, amelynek a segítségével tömören le tudunk írni bizonyos részhalmazokat egy gyűrűben. Az alábbi definíció azonban nem csak gyűrűk, hanem tetszőleges algebrai struktúrák esetén alkalmazható.
Most térjünk vissza a 18.7. szakasz végén felvetett kérdéshez. Azt már tudjuk, hogy ha egy gyűrű valamely részhalmaza magja valamilyen gyűrűhomomorfizmusnak, akkor ideál -ben. Most szeretnénk megmutatni, hogy ez visszafelé is igaz, azaz bármely ideál magja valamilyen gyűrűhomomorfizmusnak.
Ehhez szükségünk van egy konstrukcióra, amelynek a segítségével bármilyen tetszőleges ideálhoz tudunk konstruálni egy olyan gyűrűhomomorfizmust, amelynek épp lesz a magja. Ehhez azonban kell egy célgyűrű is, ahová mutatni fog. Ezt a bizonyos gyűrű és az gyűrűhomomorfizmust is az gyűrűből fogjuk képezni az ideál segítségével.
Az ötletet a 18.5. szakaszban bemutatott ábráról kölcsönözzük, amely a gyűrűhomomorfizmus szerinti maradékosztályokat szemlélteti. A 18.10. ábrán ehhez hasonlóan felcsavartuk a számegyenest olymódon, hogy az azonos maradékosztályba eső elemek azonos vonalba essenek.
Ugyan jelen esetben egy általános gyűrűről beszélünk, ahol nem sok értelme van számegyenesről beszélni, ám az analógia meglehetősen hasznos a megértéshez. A példánkban a függőleges irányban álló maradékosztály az, amelyik a gyűrűhomomorfizmus magja. Ez ugye épp a -mal osztható egész számok halmaza lesz, amelyet a 18.19. Definícióban ismertetett komplexusszorzást alkalmazva -vel jelölünk. Kérdés, hogy a többi maradékosztályt, mint halmazt hogyan tudjuk kifejezni segítségével.
Tegyük fel, hogy egy valamilyen előre rögzített egész szám, és jelöljük -mal azt a maradékosztályt, amelynek ő eleme. A továbbiakban ennek a maradékosztálynak lesz a "képviselője". Az ábrán látható, hogy -ból kiindulva az maradékosztály tetszőleges eleméhez – és csak ezekhez – eljuthatunk, ha -nak valamilyen többszöröse számú lépést teszünk meg valamilyen irányban a felcsavart számegyenesen. A 18.19. Definícióban ismertetett komplexusszorzással és komplexusösszeadással kifejezve ez azt jelenti, hogy teljesül az alábbi halmazegyenlőség:
Ezek szerint tehát a szerinti kongruencia minden maradékosztályát elő tudjuk állítani annak valamely önkényesen kiválasztott eleméből és a magjából – azaz -ből –, ami ugye a 18.17. Tétel alapján ideál -ben.
Most térjünk vissza az eredeti gyűrűhöz és annak valamely ideáljához. Az előző példával analóg módon szeretnénk valamiféle "maradékosztályokat" előállítani alakban, ahol az adott "maradékosztály" egy eleme. Az idézőjeles megfogalmazást az indokolja, hogy a 18.10. Tétel gyűrűhomomorfizmus szerinti, és nem pedig ideál szerinti maradékosztályokról beszél. Márpedig -ről egyelőre nem tudjuk, hogy vajon magja-e bármiféle gyűrűhomomorfizmusnak, hiszen épp ezt szeretnénk bizonyítani.
A gyűrűhomomorfizmus szerinti maradékosztályok tulajdonképpen a 18.9. Definícióban bevezetett gyűrűhomomorfizmus szerinti kongruenciareláció ekvivalencia-osztályai. A 18.12. Definíció utáni megjegyzés alapján két elem pontosan akkor volt kongruens egy gyűrűhomomorfizmus szerint, ha a különbségük benne volt magjában. Ezzel analóg módon talán praktikus lenne bevezetni az "ideál szerinti kongruencia" fogalmát.
Nem lesz túl meglepő, hogy a gyűrűhomomorfizmus szerinti kongruenciához hasonlóan az ideál szerinti kongruencia is egy ekvivalenciareláció. Ennek ekvivalencia-osztályai ráadásul épp a kívánt alakban írhatók fel a 18.19. Definíció szerinti komplexusösszeadás segítségével.
Az ideál szerinti kongruencia tehát eddig láthatóan ugyanúgy működik, mint a gyűrűhomomorfizmus szerinti kongruenciareláció. Mindkettő "maradékosztályokba" sorolja a gyűrű elemeit, méghozzá minden elemet pontosan egybe. Eddig azonban az ideálok tulajdonságaiból csak azt használtuk ki, hogy részgyűrűk, a 18.17. Tétel 2. pontja szerinti szorzásra vonatkozó tulajdonságot nem.
Mi azonban szeretnénk feltárni a kapcsolatot a kétféle "kongruencia"-fogalom között. Ennek érdekében egy adott ideálhoz szeretnénk keresni egy olyan gyűrűhomomorfizmust, amelynek épp a magja. Ehhez viszont szükségünk lesz egy célgyűrűre is. Ennek a célgyűrűnek – habár első hallásra furcsának tűnik – az ideál szerinti maradékosztályok lesznek az elemei, így ezek között be szeretnénk vezetni két műveletet. Az ideálok szorzással kapcsolatos tulajdonságának most lesz jelentősége.
Hogy miért hangzik furcsának bevezetni két műveletet e maradékosztályok között? Hát azért, mert ezek a maradékosztályok halmazok, márpedig műveletet általában valamilyen halmaz elemei között szokás bevezetni. A matematikában azonban semmi nem tiltja, hogy bizonyos halmazok elemei maguk is halmazok legyenek.
Emlékezzünk vissza, hogy a 13. fejezetben magukat az egész számokat is hasonlóképpen építettük fel. Akkor egy-egy természetes számokból álló párral írtunk le egy készpénz-adósság párost, és e párok között definiáltunk egy relációt, amely azt fejezte ki két ilyen párral kapcsolatban, hogy azok "azonos vagyoni helyzetet jelölnek-e" vagy nem. Erről a relációról azután megmutattuk, hogy egy ekvivalenciareláció. Az egész számok halmaza tulajdonképpen ennek a relációnak az ekvivalencia-osztályaiból áll, amelyek között vígan értelmezni tudtuk az összeadást és a szorzást, mint műveleteket.
A trükk az volt, hogy két ekvivalencia-osztály "összegének" vagy "szorzatának" meghatározásához először kiválasztottunk egy-egy tetszőleges elemet a két osztályból. Ezután ezeken elvégeztük az eredeti halmazon értelmezett megfelelő műveletet, és az eredményül kapott elem ekvivalencia-osztálya lett az ekvivalencia-osztályok közötti "összegzés" illetve "szorzás" eredménye.
Most ugyanezt a trükköt fogjuk alkalmazni, amikoris bevezetjük az "összeadást" és "szorzást" egy gyűrű ideáljának maradékosztályai között. Két maradékosztályt úgy fogunk "összeadni", illetve "összeszorozni", hogy kiválasztunk belőlük egy-egy tetszőleges elemet, amelyeket összeadunk, illetve összeszorzunk az eredeti gyűrű műveleteivel, majd azt a maradékosztályt választjuk végeredménynek, amelybe az így kapott elem esik. Egy ilyen maradékosztályok közötti műveletnek nyilvánvalóan akkor van csak értelme, ha az eredményül kapott maradékosztály nem függ attól, hogy a két bemeneti maradékosztályból mely elemeket választottuk ki a művelet elvégzéséhez. Ilyenkor mondjuk azt, hogy a művelet jóldefiniált. A 18.11. ábrán például az és maradékosztályok "összeadása" látható, amit két különböző elempár segítségével elvégezve ugyanaz az eredmény adódik:
Megköveteljük tehát, hogy függetlenül attól, hogy az vagy az "összeget" számítjuk-e ki az eredeti gyűrűben, az eredménynek mindkét esetben ugyanabba a maradékosztályba kell esnie. Természetesen ugyanezt megköveteljük a "szorzásra" is.
Tekintsünk először egy, az gyűrűből kiinduló gyűrűhomomorfizmust, és vizsgáljuk meg, hogy ha az szerinti maradékosztályok között kéne ugyanilyen módon "összeadást" vagy "szorzást" definiálni, akkor vajon ezek a műveletek jóldefiniáltak lennének-e ebben az értelemben. Ekkor az , és a kongruenciák épp azt jelentik, hogy teljesülnek az
egyenletek.
Ez viszont összegtartó tulajdonságából következően a 18.12. Definíció utáni megjegyzés alapján épp azt jelenti, hogy az és különbségek benne vannak magjában, azaz -ben. Ám a 18.17. Tétel miatt részgyűrű -ben, és így zárt az összeadásra. Ez alapján e két különbség összege, azaz
szintén benne van -ben, azaz teljesül az kongruencia.
Az "összeadás" tehát valóban jóldefiniált, hiszen ugyanabba a maradékosztályba eső eredményt kapunk, függetlenül attól, hogy mely elemeket választjuk ki a művelet elvégzéséhez a két bemeneti maradékosztályból.
A "szorzás" jóldefiniáltsága szorzattartó tulajdonságából következik. Szorozzuk ugyanis össze a fenti két egyenletet:
Nekünk azonban az ideál szerinti maradékosztályok esetén volna szükségünk egy ugyanilyen jellegű jóldefiniáltságra. Kérdés, hogy ez vajon ezekre a maradékosztályokra is teljesül-e. Ezt biztosítja az alábbi tétel.
Ez tehát azt jelenti, hogy az ideál szerinti maradékosztályok esetén is teljesülne a jóldefiniáltság a bevezetendő műveleteinkre. Egyre több jel mutat arra, hogy a gyűrűhomomorfizmus szerinti kongruencia és az ideál szerinti kongruencia fogalma tulajdonképpen egy és ugyanaz. Szedjük is össze az eddig megtalált párhuzamokat:
- Két elem között mindkettő pontosan akkor teljesül, ha a különbségük benne van egy bizonyos halmazban. Egyik esetben ez annak a gyűrűhomomorfizmusnak a magja, másik esetben pedig az az ideál, amely szerint képeztük az adott "kongruenciát".
- Mindkettő ekvivalenciareláció.
- Mindkettőnek a "maradékosztályai" teljesen ugyanúgy fejezhetők ki a 18.19. Definíció szerinti komplexusműveletek segítségével.
- E "maradékosztályok" között mindkettő esetben ugyanúgy értelmezhetünk jóldefiniált műveleteket.
Ha ez a két fogalom valóban ugyanaz, akkor az egyben azt is jelenti, hogy egy gyűrűből kiinduló gyűrűhomomorfizmusok magjai és az adott gyűrű ideáljai pontosan ugyanazok a halmazok lesznek. Visszautalnánk a 18.17. Tételre, amelyben már láttuk, hogy a gyűrűhomomorfizmusok magjai mind ideálok. Most azt fogjuk megmutatni, hogy ez visszafelé is igaz. Ez az alábbi tétel közvetlen következménye lesz, amely az ideál szerinti maradékosztályok halmazán az imént ismertetett módon bevezetendő műveletek tulajdonságairól szól.
Az imént bizonyított és a 18.17. Tétel következményeként mostmár egyértelműen azonosítani tudjuk egy gyűrű azon részhalmazait, amelyek valamilyen gyűrűhomomorfizmusok magjai lehetnek. Erről szól az alábbi következmény.
Ez tehát azt jelenti, hogy a 18.9. Definícióban bevezetett gyűrűhomomorfizmus szerinti kongruencia fogalma helyett nyugodtan használhatjuk a továbbiakban a 18.20. Definícióban bevezetett ideál szerinti kongruencia fogalmát. A 18.13. Tétel alapján ugyanis egy gyűrűhomomorfizmus szerinti kongruencia nem függ a konkrét gyűrűhomomorfizmustól, hanem annak csakis a magjától. Most viszont épp azt bizonyítottuk, hogy bármely gyűrű esetén a belőle kiinduló gyűrűhomomorfizmusok magjai épp egybeesnek ideáljaival. Így tehát ideáljainak ismeretében az összes létező kongruenciarelációt megkaphatjuk, ami csak értelmezhető -en.
18.9Gyűrűk homomorfizmustétele
Az előző szakaszban ismertetett meglehetősen absztrakt fogalmakra most egy kézenfekvő példát mutatunk. Fentebb már előkerült a halmaz, amely a -mal osztható egész számokat tartalmazza. Erről már megállapítottuk, hogy ő egy ideál -ben. Mi történik, ha -t ezzel az ideállal faktorizáljuk, azaz képezzük a maradékosztálygyűrűt? Ennek három eleme lesz, méghozzá a ideál szerinti maradékosztályok. A 18.19. Definícióban ismertetett komplexusszorzással és komplexusösszeadással kifejezve ezek a maradékosztályok a következők:
Ezek tehát azokból az egész számokból fognak állni, amelyek -mal osztva rendre , illetve maradékot adnak. Az ezek közötti műveleteket a 18.23. Tétel alapján könnyen elvégezhetjük. Például az és a maradékosztályok összege a , szorzata pedig a maradékosztály lesz. Vezessük be az alábbi jelöléseket:
Ekkor a maradékosztálygyűrű műveleti táblái így néznek ki:
Ha összehasonlítjuk ezeket a táblázatokat a 18.1. szakaszban bemutatott gyűrű műveleti tábláival, akkor azt tapasztaljuk, hogy szinte megegyeznek egymással, eltekintve a jelölésbeli különbségektől. Algebrai szóhasználattal élve úgy tűnik, mintha a és gyűrűk izomorfak lennének. Íme a gyűrű műveleti táblái:
Ez nem véletlenül van így! Emlékezzünk csak vissza, hogy a gyűrű tulajdonképpen nem más, mint egy -ből kiinduló gyűrűhomomorfizmus, – nevezetesen a maradékképző függvény – képe. Ráadásul ennek a gyűrűhomomorfizmusnak a magja épp a -mal osztható egész számok halmaza, azaz . Ez éppenséggel az az ideál, amelynek a segítségével a faktorgyűrűt képeztük.
Az alábbi tétel szerint általánosságban is igaz, hogyha egy gyűrűt egy belőle kiinduló gyűrűhomomorfizmus magjával faktorizálunk, akkor az így kapott faktorgyűrű izomorf lesz képével.
Bizonyítás:
Előszöris megjegyezzük, hogy a 18.17. Tétel alapján ideál -ben, így a bizonyítandó állításban szereplő gyűrűizomorfizmus baloldala a 18.23. Tétel szerint valóban egy gyűrű, nevezetesen az faktorgyűrű. Igaz továbbá, hogy a 18.16. Tétel alapján részgyűrű abban a gyűrűben, ahová mutat, így a jobboldal is egy gyűrű. Az
kifejezés tehát értelmes, mert tényleg egy gyűrűizomorfizmust jelöl. Most megmutatjuk, hogy ez a gyűrűizomorfizmus valóban fennáll a két gyűrű között.
Az faktorgyűrű elemei a – mint ideál – szerinti maradékosztályok. Ezek a 18.12. Definíció utáni megjegyzés alapján pontosan ugyanazok a maradékosztályok lesznek, mint a 18.9. Definíció által definiált gyűrűhomomorfizmus szerinti maradékosztályok. Most megadunk egy
leképezést e faktorgyűrű és az gyűrűhomomorfizmus képe – azaz – között.
Ennek a leképezésnek az alábbi képletét az gyűrű elemeinek és az gyűrűhomomorfizmusnak a segítségével konstruáljuk meg. A képlet azt fejezi ki, hogy minden elem esetén a leképezés az -et tartalmazó maradékosztályhoz épp azt az elemet rendeli hozzá a célgyűrűből – azaz -ből –, amelyet az gyűrűhomomorfizmus is hozzárendel magához az elemhez:
A 18.12. ábra mutatja a leképezés iménti konstrukcióját.
Ez egy értelmes leképezés, ha ugyanis valamely és elemek ugyanabban a szerinti maradékosztályban vannak, akkor a 18.20. Definíció szerint az ő különbségük benne van a ideálban. Ez viszont ugye magja, tehát a 18.12. Definíció utáni megjegyzés alapján ez épp azt jelenti, hogy az szerinti képük megegyezik. Vagyis a leképezés eredménye nem függ attól, hogy a bemeneti maradékosztály mely reprezentánselemének segítségével számítottuk azt ki a fenti képlettel.
Azt kell még igazolni, hogy a leképezés bijektív, ami a 18.6. Definíció alapján azt jelenti, hogy egyszerre injektív és szürjektív. Az injektivitáshoz azt kell megmutatnunk, hogy egymástól különböző maradékosztályok szerinti képe is különbözik. Tegyük fel ezért indirekt, hogy az gyűrű és elemei két egymástól különböző maradékosztályt reprezentálnak, ám e két maradékosztálynak ennek ellenére ugyanaz a szerinti képe, azaz:
Ez a leképezés definíciója alapján azt jelentené, hogy:
De ez ellentmondás, hiszen ez azt jelentené, hogy és mégis ugyanabban a maradékosztályban vannak. Tehát valóban injektív.
Most igazoljuk a szürjektivitást. Ez a 18.6. Definíció alapján azt jelenti, hogy célgyűrűben nincs olyan elem, amely ne lenne képe valamely maradékosztálynak a leképezés szerint. Ez viszont természetesen teljesül, hiszen a célgyűrű nem más, mint , azaz az gyűrűhomomorfizmus képe. Következésképp minden itt lévő elemhez létezik olyan elem az gyűrűben, amelyre
teljesül. Ez épp azt jelenti, hogy az elem benne van az maradékosztályban, amelyhez viszont a leképezés rendeli hozzá az elemet a célgyűrűben. A függvény tehát valóban szürjektív.
Ennek alkalmazásához most visszautalnánk a 18.6. szakaszban a 18.13. Tétel kapcsán felvetett példára. Ez a tétel szólt arról, hogy egy gyűrűhomomorfizmus szerinti kongruenciát kizárólag magja, nem pedig maga határoz meg. Ennek demonstrálásához képeztünk két különböző, de azonos magú gyűrűhomomorfizmust az egész számok gyűrűjéből két másik gyűrűre. Ezek közül az egyik a 18.3. Definícióból már jól ismert kételemű gyűrű volt. A másik gyűrűt az említett szakaszban -vel jelöltük, és alaphalmaza az és betűket tartalmazta. Ennek a meglehetősen mesterkélt gyűrűnek a műveleteit a műveleti tábláival adtuk meg. Azt tapasztaltuk, hogy a két gyűrű csak az elemek elnevezésében és a használt műveleti jelekben tért el egymástól, de ezeken kívül teljesen ugyanaz volt a szerkezetük. Azaz izomorfak voltak egymással.
Nos, ez az imént bizonyított homomorfizmustétel következménye. A és gyűrűkbe mutató két gyűrűhomomorfizmusnak ugyanis megegyezett a magja, amely ugye – mint ahogy azt a 18.24. Következmény alapján már tudjuk – egy ideál -ben. Következésképp a homomorfizmustétel miatt mindkét gyűrű izomorf a gyűrű ezen ideál szerinti faktorgyűrűjével, és így a a 18.6. Definíció utáni megjegyzés alapján egymással is.
Ebben a fejezetben tehát megismerkedtünk a Diffie-Hellman kulcscsere protokollban és az RSA-eljárásban használt moduláris aritmetika matematikai alapjaival. Ennek kapcsán megismerkedtünk olyan gyűrűkkel, amelyeknek csak véges sok elemük van, és meg is tanultunk számolni ezekben a gyűrűkben. Ehhez kulcsfontosságú volt a gyűrűhomomorfizmus fogalmának megismerése, amelynek a segítségével mellesleg igazoltuk a Diffie-Hellman kulcscsere protokoll helyességét. Ezután tetszőleges gyűrűkben azonosítottuk azokat a részhalmazokat, amelyek valamilyen gyűrűhomomorfizmusok magjai lehetnek. Mindeközben megismerkedtünk a kongruenciák, az ideálok és a maradékosztálygyűrűk fogalmával.
A következő fejezetben az ideálok segítségével végleg lezárjuk a számelmélet alaptételének kérdését. Ennek során megismerkedünk az úgynevezett "főideálgyűrűkkel", majd a 20. fejezettől kezdve az egész számokon értelmezett kongruenciákat fogjuk tanulmányozni.