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 a^n kifejezést egy olyan szorzatként kell értelmezni, amelynek n darab tényezője van, és minden tényezője a. Azaz:
A moduláris hatványozást ugyanígy egy n 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 4\cdot 5 szorzatot kellett kiszámítani a 11 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 4\cdot 5=20 lépést kell megtenni az óralapon. Ezután a 0-ból kiindulva az óramutató járásával megegyező irányban megtettük a 20 lépést. A végeredmény az a szám lett, ahová megérkeztük, azaz 9. 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 11 elemű óralapon lépkedünk, akkor a lépegetés során a 11 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 20 – mennyi maradékot ad 11-gyel osztva. A végeredmény a keresett maradék lesz. Jelen esetben a 20 és a 11 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 2^{328} 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 328 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 2^{328} részeredmény egészen pontosan 329 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ő 265 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 5 és 3 egész számok között kétféleképpen is elvégezhetjük a maradékos osztást:
Első esetben 2, második esetben pedig -1 lesz a maradék. Mindkettő helyes, hiszen a \Z 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 3. 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 a egész számhoz hozzá tudunk rendelni egy nemnegatív maradékot, amelyet a-nak egy valamilyen m\neq 0 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 m darab olyan nemnegatív egész szám létezik, amely maradékként szóba jöhet, azaz értéke kisebb, mint m abszolút értéke. Például m=3 vagy m=-3 esetén ezek a 0, az 1 és a 2 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 m=3. Ekkor ugye a Z_3 halmazról van szó, amelynek mindössze a 0, az 1 és a 2 lesznek az elemei. Az alábbiakban a \bmod_3 függvény néhány hozzárendelését tüntettük fel:
Az alábbi két táblázatban pedig a Z_3 halmazon értelmezett \oplus és \odot műveletek úgynevezett "műveleti táblái" láthatók:
Például a 2\oplus 1 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 0. A műveletet a fenti definíció szerint elvégezve valóban 0-t kapunk, hiszen
Az 1\oplus 2 eredménye ehhez hasonlóan az első sor második oszlopában szerepel, ami – hatalmas meglepetésre – szintén 0. A moduláris szorzás táblázata ugyanígy értelmezendő. Például 2\odot 2=1. Nyilván, hiszen ha 2\cdot 2-t elosztjuk 3-mal, akkor épp 1 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 Z_m gyűrűben
Eszerint tehát amikor modulo m 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 Z_m 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 2x+3=7 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:
A 12.18. Lemma, amely szerint tetszőleges a, b és c természetes számokra
esetén a=b következik.
A 14.2. Lemma, amely szerint tetszőleges a, b és c\neq 0 természetes számokra
esetén szintén a=b következik.
Most térjünk vissza a szóbanforgó egyenletünkhöz. Első lépésként az egyenlet jobboldalát 7 helyett egy kéttagú összegként írtuk fel:
Ebből a 12.18. Lemma alapján 2x=4 következik.
Ezután második lépésként ennek jobboldalát 4 helyett egy kéttényezős szorzatként írtuk fel:
Ebből viszont a 14.2. Lemma alapján az x=2 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 Z_m gyűrű minden m\neq 0 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 Z_8 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 3 ellentettjét. A Z_8 gyűrűben ez az 5 lesz, hiszen a moduláris összeadás 18.3. Definíciója alapján
A baloldalon tehát 2\odot x marad, míg a jobboldalon 4-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ő 4-et egy kéttényezős szorzatként 2\odot 2 alakban:
Ha azonban most meggondolatlanul alkalmazzuk szépen a 15.4. Tételt, és erre hivatkozva mindkét oldalt "egyszerűsítjük" 2-vel, akkor könnyen azt a következtetést vonhatjuk le, hogy a fenti egyenletből x=2 következik.
Ez azonban hibás érvelés! Az x=2 valóban megoldása a
egyenletnek, azonban van még egy további megoldás is. Nevezetesen az x=6, amely fölött ezzel a lépéssel szépen átsiklunk.
Ellenőrizzük csak le, hogy a Z_8 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 Z_8-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 Z_8 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 0, amikor történetesen egyik tényezője sem az. Ilyen például a 2\odot 4 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 Z_m 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 a és n\gt 0 egész számok esetén számítsuk ki azt a maradékot, amelyet az a^n hatvány ad valamilyen m\neq 0 egész számmal osztva. A konkrét feladatban a 2^{328} hatvány 11-gyel való osztási maradékát kellett kiszámítani. A probléma ugye az, hogy ezt az a^n hatvány tényleges kiszámítása nélkül kellene megtennünk, máskülönben a modulo m maradékképzés előtt kapott részeredmény kezelhetetlenül nagy lenne.
Azt viszont láttuk a 18.2. szakaszban, hogy a Z_m 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 Z_m 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 Z_m gyűrűbe és ott végezzük el a moduláris szorzásokat, akkor ugyanazt kell kapnunk, mintha előbb a \Z gyűrűben végeznénk el a hagyományos szorzásokat, majd vennénk az így kapott eredmény Z_m-beli megfelelőjét.
A 13.5. szakaszban a természetes számok \Z-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 \Z és Z_m 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):
Legyen adva egy (R,+,\cdot) és egy (S,\oplus,\odot) gyűrű, továbbá egy
függvény a két gyűrű alaphalmaza között.
Tegyük fel továbbá, hogy tetszőleges R-beli a és b elemekre teljesülnek az alábbi követelmények:
Ekkor az f függvényt gyűrűhomomorfizmusnak nevezzük.
Amennyiben S minden eleme legalább egy R-beli elemhez hozzá van rendelve f által, akkor f-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 S minden eleme legfeljebb egy R-beli elemhez van hozzárendelve f által, akkor f-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 S minden eleme pontosan egy R-beli elemhez van hozzárendelve f által, akkor f-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 R és az S 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 f(a)=a leképezés nyilvánvalóan gyűrűizomorfizmus R-ből önmagába.
Nyilván, hiszen ha a nyilak irányát megfordítjuk, akkor az így kapott fordított irányú g leképezés is kölcsönösen egyértelmű. Ez azt jelenti, hogy ha x_S az S gyűrű tetszőleges eleme, akkor létezik olyan x_R elem az R gyűrűben, amelyre teljesülnek az alábbiak:
Ekkor azonban f művelettartó tulajdonságai, valamint a fentiek miatt teljesülnek az alábbi egyenletek:
A g leképezés tehát szintén gyűrűizomorfizmus, csak épp S-ből mutat R-be.
Jelöljük ugyanis f_{RS}-sel az R-ből S-be mutató, f_{ST}-vel pedig az S-ből T-be mutató gyűrűizomorfizmust. Ezek után definiáljuk az R-ből közvetlenül T-be mutató g leképezést f_{RS} és f_{ST} egymás után alkalmazásaként. Azaz tetszőleges R-beli x elemre legyen
A 18.5. ábrán azonnal látszik, hogy az R-ből T-be mutató g leképezés tulajdonképpen az f_{RS} és f_{ST} leképezéseket reprezentáló nyilak összekapcsolása, amely nyilván kölcsönösen egyértelmű:
A művelettartó tulajdonságok könnyen adódnak az f_{RS} és f_{ST} gyűrűizomorfizmusok hasonló tulajdonságaiból. Az alábbi levezetésben az R gyűrű műveleteit a + és \cdot, az S gyűrű műveleteit a \oplus és \odot, végül a T gyűrű műveleteit a \boxplus és \boxdot szimbólumokkal jelöltük:
Az alábbi tételben meg is adunk egy gyűrűhomomorfizmust az egész számok \Z gyűrűjéből a véges sok elemet tartalmazó Z_m 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 2^{328} hatvány mennyi maradékot ad 11-gyel osztva. Ehhez annyit kell tennünk, hogy a 328 darab tényezőre alkalmazzuk a \bmod_{11} maradékképző függvényt, és az így kapott maradékokon elvégezzük a moduláris szorzást a Z_{11} gyűrűben. Mivel az imént bizonyított 18.7. Tétel alapján a \bmod_{11} függvény egy gyűrűhomomorfizmus \Z és Z_{11} 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 Z_m 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 Z_m 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 x egész számban és egy m\neq 0 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 a, Bob-é pedig b. Ezeket a kitevőket egymásnak sem árulják el.
Ezután Alice a Z_m gyűrűben elvégzi az x^a moduláris hatványozást, és az eredményt átküldi Bobnak. Bob ugyanígy elvégzi az x^b 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 x^b számra elvégzi az (x^b)^a, Bob pedig az Alice-tól kapott x^a számra elvégzi az (x^a)^b 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 R és egy S gyűrű, valamint egy közöttük lévő f:R\to S művelettartó leképezés, azaz gyűrűhomomorfizmus. Ez tehát R minden eleméhez hozzárendel valamilyen S-beli elemet. Elképzelhető azonban, hogy egy adott S-beli elem több R-beli elemhez is hozzá van rendelve. Így tehát R elemei között definiálhatunk egy relációt, amely azt fejezi ki két R-beli elem között, hogy nekik ugyanaz az f gyűrűhomomorfizmus szerinti képük az S 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 f 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 f gyűrűhomomorfizmus az R gyűrűt maradékosztályokra bontja, és egy adott maradékosztályban minden elemnek ugyanaz lesz az f szerinti képe az S gyűrűben. A 18.6. ábrán például a \Z és Z_3 gyűrűk között lévő, a 18.3. Definícióban már ismertetett \bmod_3 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 3-mal osztva azonos maradékot adnak. Az ábra jobboldalán a \bmod_3 gyűrűhomomorfizmus képhalmaza, tehát jelen esetben a Z_3 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 \bmod_3 leképezést nyilakkal szemléltettük, amely tehát minden egész számhoz az ő modulo 3 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 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 f 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 R gyűrű, valamint egy ezen értelmezett f gyűrűhomomorfizmus, de nem ismerjük azt az S gyűrűt, amelybe f képez. Szeretnénk azonban feltárni S szerkezetét. Hamarosan látni fogjuk, hogy ehhez előszöris az f szerinti kongruenciareláció által kijelölt R-beli maradékosztályokat kell meghatároznunk.
Első körben azt gondolnánk, hogy erre nincs más mód, mint R összes elemére alkalmazni az f 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 f ö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 R gyűrűből kiinduló, S gyűrűbe mutató valamilyen f 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 R-beli elemekből áll, amelyekhez az f leképezés az S gyűrű nullelemét rendeli hozzá. Ennek a kitüntetett maradékosztálynak, valamint az f é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 R és S tetszőleges gyűrűk, valamint legyen adva közöttük egy f:R\to S gyűrűhomomorfizmus. Ekkor az f gyűrűhomomorfizmus magjának nevezzük azon R-beli elemek halmazát, melyeknek f szerinti képe az S gyűrű nulleleme. Az f magját – az angol "kernel" szóból eredeztetve – így jelöljük:
Az f gyűrűhomomorfizmus képének nevezzük azoknak az S-beli elemeknek a halmazát, amelyek képei legalább egy R-beli elemnek. Az f 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 \Z és Z_3 közötti \bmod_3 maradékképző függvény – mint gyűrűhomomorfizmus – magja épp a 3-mal osztható egész számokból áll. A \bmod_3 függvény ugyanis pontosan ezekhez rendeli hozzá a Z_3 gyűrű nullelemét, azaz a 0 maradékot. A \bmod_3 függvény képe pedig a 18.3. Definíció utáni megjegyzés 5. pontja miatt maga a Z_3 halmaz.
Megjegyezzük továbbá, hogy egy f:R\to S 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 R gyűrű nullelemét, hiszen ennek képe biztosan az S 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 f gyűrűhomomorfizmus szerinti kongruenciarelációt kizárólag annak magja, nem pedig maga f határozza meg. Még csak az sem érdekes, hogy f 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 Z_2 gyűrű. A másik célgyűrű elsőre szokatlan lesz, mivel ennek alaphalmaza nem számokból, hanem az e és az o betűkből áll. Ezt a halmazt P-vel fogjuk jelölni a példában. Vezessünk be ezen a halmazon is két műveletet, jelöljük őket a \boxplus és a \boxdot szimbólumokkal, és definiáljuk őket önkényesen az alábbi műveleti táblákkal:
Könnyű leellenőrizni, hogy a P halmaz ezzel a két művelettel szintén gyűrűt alkot, melynek nulleleme az e betű, egységeleme pedig az o betű. Ennek legegyszerűbb módja, ha meggondoljuk, hogy ez a gyűrű Z_2-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 h leképezés tulajdonképpen egy 18.6. Definíció szerinti gyűrűizomorfizmus a Z_2 és a P gyűrűk között, azaz Z_2\simeq P:
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 \Z gyűrűje, valamint van két célgyűrűnk: a Z_2 és az imént definiált, meglehetősen szokatlan P. Nincs más hátra, mint találni két \Z-ből kiinduló gyűrűhomomorfizmust, amelyeknek ugyanaz a magja \Z-ben, azonban az egyiknek a célgyűrűje Z_2, a másiknak pedig P.
Az első viszonylag egyszerű, hiszen a 18.3. Definíció szerinti \bmod_2 maradékképző függvény a 18.7. Tétel alapján egy gyűrűhomomorfizmus \Z és Z_2 között. Ennek magja a 2-vel osztható – tehát páros – számokból áll, hiszen pontosan ezek fognak 0 maradékot adni 2-vel osztva.
A másik gyűrűhomomorfizmust az alábbi f függvénnyel adjuk meg:
Az Olvasóra bízzuk annak átgondolását, hogy f valóban egy gyűrűhomomorfizmus \Z és P között. Mivel az e betű a P gyűrű nulleleme, ezért az f 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ő \bmod_2:\Z\to Z_2 és f:\Z\to P 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 a és b 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 R 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ő R-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 2\Z-vel jelölt halmaza maga is gyűrű a \Z-n értelmezett összeadásra és szorzásra nézve, így 2\Z részgyűrű \Z-ben. Mivel nem minden egész szám páros, ezért 2\Z\lt \Z, azaz 2\Z valódi részgyűrű \Z-ben. A páratlan számok szintén részhalmazt alkotnak \Z-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 3+5=8, 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 R 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 S 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 S gyűrű esetén tehát az odamutató gyűrűhomomorfizmusok képeiről mindössze annyit tudunk mondani, hogy azok pontosan S részgyűrűi lesznek. Ezzel szemben egy R gyűrű azon részhalmazairól, amelyek valamilyen, R-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 f gyűrűhomomorfizmust, amelynek I a magja. Ez egy valamilyen, számunkra ismeretlen X gyűrűbe képez, amelynek nullelemét jelöljük most 0_X-szel, míg az R gyűrű nullelemét jelöljük 0_R-rel. Az f függvény tehát I minden eleméhez 0_X-et rendeli hozzá, hiszen \ker f=I. Ezt a szituációt mutatja a 18.9. ábra.
Az 1. tulajdonság igazolásához azt kell megmutatni, hogy I részgyűrű R-ben. Ez a 18.15. Tétel alapján pontosan akkor teljesül, ha I tartalmazza 0_R-t, valamint zárt az R gyűrű mindkét műveletére és az R-beli ellentettképzésre.
Mivel f 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 f(0_R)=0_X, és így 0_R valóban benne van f magjában, azaz I-ben. Másrészt ha valamilyen a benne van I-ben, akkor f(a)=0_X, és így az ellentettképzés tartása miatt
Azaz a ellentettjének is 0_X a képe, következésképp ő is benne van I-ben.
Az összeadásra való zártság szintén f összegtartó tulajdonságából ered. Ha ugyanis a és b az I 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 a+b összeg is az X gyűrű nullelemére képeződik, következésképp ő is benne van I-ben. A szorzásra való zártság teljesen hasonló módon következik f szorzástartó tulajdonságából. Mivel teljesül a 18.15. Tétel szerinti összes feltétel, ezért I valóban részgyűrű R-ben.
A 2. tulajdonság igazolásához tegyük fel, hogy r az R gyűrű tetszőleges – tehát nem feltétlenül I-beli – eleme. Azt kell megmutatni, hogy amennyiben ezzel akár balról, akár jobbról megszorzunk egy I-beli a elemet, akkor az eredmény is I-beli lesz. Mivel a benne van I-ben, ezért f(a)=0_X. Következésképp f szorzástartó tulajdonsága miatt az r\cdot a és a\cdot r szorzatok képére igazak lesznek az alábbiak:
Elképzelhető ugyan, hogy a két szorzatnak nem ugyanaz lesz az eredménye az R gyűrűben – kivéve persze ha kommutatív gyűrűről van szó –, de az biztos, hogy mindkét szorzat f szerinti képe az X gyűrű nulleleme lesz. Következésképp valóban benne vannak I-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 \Z gyűrűjében ideált alkot a páros számok 2\Z-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ű \Z-ben.
Az iménti definícióban megismert szóhasználattal élve a 18.17. Tétel úgy is megfogalmazható, hogy amennyiben egy R gyűrű valamely I részhalmaza magja valamilyen gyűrűhomomorfizmusnak, akkor I ideál R-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 R gyűrű valamely I részhalmaza magja valamilyen gyűrűhomomorfizmusnak, akkor I ideál R-ben. Most szeretnénk megmutatni, hogy ez visszafelé is igaz, azaz bármely I 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 I ideálhoz tudunk konstruálni egy olyan f gyűrűhomomorfizmust, amelynek épp I lesz a magja. Ehhez azonban kell egy célgyűrű is, ahová f mutatni fog. Ezt a bizonyos gyűrű és az f gyűrűhomomorfizmust is az R gyűrűből fogjuk képezni az I ideál segítségével.
Az ötletet a 18.5. szakaszban bemutatott ábráról kölcsönözzük, amely a \bmod_3 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 \bmod_3 gyűrűhomomorfizmus magja. Ez ugye épp a 3-mal osztható egész számok halmaza lesz, amelyet a 18.19. Definícióban ismertetett komplexusszorzást alkalmazva 3\Z-vel jelölünk. Kérdés, hogy a többi maradékosztályt, mint halmazt hogyan tudjuk kifejezni 3\Z segítségével.
Tegyük fel, hogy a egy valamilyen előre rögzített egész szám, és jelöljük [a]_3-mal azt a maradékosztályt, amelynek ő eleme. A továbbiakban ennek a maradékosztálynak a lesz a "képviselője". Az ábrán látható, hogy a-ból kiindulva az [a]_3 maradékosztály tetszőleges eleméhez – és csak ezekhez – eljuthatunk, ha 3-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 \bmod_3 szerinti kongruencia minden maradékosztályát elő tudjuk állítani annak valamely önkényesen kiválasztott eleméből és a \bmod_3 magjából – azaz 3\Z-ből –, ami ugye a 18.17. Tétel alapján ideál \Z-ben.
Most térjünk vissza az eredeti R gyűrűhöz és annak valamely I ideáljához. Az előző példával analóg módon szeretnénk valamiféle "maradékosztályokat" előállítani r+I alakban, ahol r 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 I-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 f gyűrűhomomorfizmus szerint, ha a különbségük benne volt f 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 I ideálhoz szeretnénk keresni egy olyan gyűrűhomomorfizmust, amelynek épp I 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 I 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 \Z 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 R gyűrű I 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 R 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 M és N 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 a_1+b_1 vagy az a_2+b_2 "ö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 R gyűrűből kiinduló f gyűrűhomomorfizmust, és vizsgáljuk meg, hogy ha az f 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 a_1\equiv a_2\pod f, és a b_1\equiv b_2\pod f kongruenciák épp azt jelentik, hogy teljesülnek az
egyenletek.
Ez viszont f összegtartó tulajdonságából következően a 18.12. Definíció utáni megjegyzés alapján épp azt jelenti, hogy az a_1-a_2 és b_1-b_2 különbségek benne vannak f magjában, azaz \ker f-ben. Ám \ker f a 18.17. Tétel miatt részgyűrű 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 \ker f-ben, azaz teljesül az a_1+b_1\equiv a_2+b_2\pod f 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 f szorzattartó tulajdonságából következik. Szorozzuk ugyanis össze a fenti két egyenletet:
A szorzattartó tulajdonság miatt ekkor:
Ez viszont épp azt jelenti, hogy teljesül az a_1\cdot b_1\equiv a_2\cdot b_2\pod f kongruencia.
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 R gyűrű esetén a belőle kiinduló gyűrűhomomorfizmusok magjai épp egybeesnek R ideáljaival. Így tehát R ideáljainak ismeretében az összes létező kongruenciarelációt megkaphatjuk, ami csak értelmezhető R-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 3\Z halmaz, amely a 3-mal osztható egész számokat tartalmazza. Erről már megállapítottuk, hogy ő egy ideál \Z-ben. Mi történik, ha \Z-t ezzel az ideállal faktorizáljuk, azaz képezzük a \Z/3\Z maradékosztálygyűrűt? Ennek három eleme lesz, méghozzá a 3\Z 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 3-mal osztva rendre 0, 1 illetve 2 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 1+3\Z és a 2+3\Z maradékosztályok összege a 0+3\Z, szorzata pedig a 2+3\Z maradékosztály lesz. Vezessük be az alábbi jelöléseket:
Ekkor a \Z/3\Z 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 Z_3 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 Z_3 és \Z/3\Z gyűrűk izomorfak lennének. Íme a Z_3 gyűrű műveleti táblái:
Ez nem véletlenül van így! Emlékezzünk csak vissza, hogy a Z_3 gyűrű tulajdonképpen nem más, mint egy \Z-ből kiinduló gyűrűhomomorfizmus, – nevezetesen a \bmod_3 maradékképző függvény – képe. Ráadásul ennek a gyűrűhomomorfizmusnak a magja épp a 3-mal osztható egész számok halmaza, azaz 3\Z. Ez éppenséggel az az ideál, amelynek a segítségével a \Z/3\Z faktorgyűrűt képeztük.
Az alábbi tétel szerint általánosságban is igaz, hogyha egy R gyűrűt egy belőle kiinduló f gyűrűhomomorfizmus magjával faktorizálunk, akkor az így kapott faktorgyűrű izomorf lesz f képével.
Bizonyítás:
Előszöris megjegyezzük, hogy a 18.24. Következmény alapján \ker f ideál R-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 R/\ker f faktorgyűrű. Igaz továbbá, hogy a 18.16. Tétel alapján \text{im} f részgyűrű abban a gyűrűben, ahová f 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 átláthatóság érdekében vezessük be az I=\ker f jelölést. Az R/I faktorgyűrű elemei tehát az I – 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 f gyűrűhomomorfizmus szerinti maradékosztályok. Most megadunk egy
leképezést e faktorgyűrű és az f gyűrűhomomorfizmus képe – azaz \text{im} f – között.
Ennek a leképezésnek az alábbi képletét az R gyűrű elemeinek és az f gyűrűhomomorfizmusnak a segítségével konstruáljuk meg. A képlet azt fejezi ki, hogy minden r elem esetén a g leképezés az r-et tartalmazó maradékosztályhoz épp azt az elemet rendeli hozzá a célgyűrűből – azaz \text{im} f-ből –, amelyet az f gyűrűhomomorfizmus is hozzárendel magához az r elemhez:
A 18.12. ábra mutatja a g leképezés iménti konstrukcióját.
Ez egy értelmes leképezés, ha ugyanis valamely r_1 és r_2 elemek ugyanabban az I szerinti maradékosztályban vannak, akkor a 18.20. Definíció szerint az ő különbségük benne van az I ideálban. Ez viszont ugye f magja, tehát a 18.12. Definíció utáni megjegyzés alapján ez épp azt jelenti, hogy az f szerinti képük megegyezik. Vagyis a g 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 g 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 g szerinti képe is különbözik. Tegyük fel ezért indirekt, hogy az R gyűrű r és 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 g szerinti képe, azaz:
Ez a g leképezés definíciója alapján azt jelentené, hogy:
De ez ellentmondás, hiszen ez azt jelentené, hogy r és s mégis ugyanabban a maradékosztályban vannak. Tehát g 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 g leképezés szerint. Ez viszont természetesen teljesül, hiszen a célgyűrű nem más, mint \text{im} f, azaz az f gyűrűhomomorfizmus képe. Következésképp minden itt lévő s elemhez létezik olyan x elem az R gyűrűben, amelyre
teljesül. Ez épp azt jelenti, hogy az x elem benne van az x+I maradékosztályban, amelyhez viszont a g leképezés rendeli hozzá az s elemet a célgyűrűben. A g függvény tehát valóban szürjektív.
Végül g művelettartási tulajdonságai az őt definiáló képletből már könnyen adódnak. Az alábbi levezetésben az eredeti R gyűrű műveleteit a szokásos + és \cdot, az R/I faktorgyűrű műveleteit a \oplus és \odot, végül az \text{im} f célgyűrű műveleteit a \boxplus és \boxdot szimbólumokkal jelöltük:
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 f gyűrűhomomorfizmus szerinti kongruenciát kizárólag f magja, nem pedig maga f 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 \Z 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ű Z_2 gyűrű volt. A másik gyűrűt az említett szakaszban P-vel jelöltük, és alaphalmaza az e és o 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 Z_2 és P 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 \Z-ben. Következésképp a homomorfizmustétel miatt mindkét gyűrű izomorf a \Z 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.