Episode I

Alice és Bob

24. rész: Alice és Bob komolyabb fegyverekhez nyúl

Az előző részben felhívtuk Alice és Bob figyelmét néhány olyan dologra, amelyekre érdemes odafigyelniük a 21. részben ismertetett RSA-kulcsok generálásakor. Ismertettünk továbbá néhány olyan módszert, amelyeknek a segítségével Alice és Bob kellően nagy prímszámokat tud találni ezekhez a kulcsokhoz. Elsőként az „iskolás módszert” vizsgáltuk meg, amely a prímszámok definíciójának megfelelően osztáspróbákon alapul. Láttuk, hogy ez nem egy járható út, mivel a kérdéses számtartományban túlságosan sokáig tart. Ezután bemutattuk az úgynevezett Fermat-prímtesztet, amely ennél jóval gyorsabb, cserébe viszont nagyon kis valószínűséggel ugyan, de tévedhet. Az igazi hátránya azonban az, hogy léteznek olyan univerzális álprímeknek nevezett számok, amelyek esetén viszont majdnem biztosan hibás eredményt ad. Ezért megismerkedtünk a Miller-Rabin-prímteszttel, amely a Fermat-prímteszt egy továbbfejlesztett változata. Ez látszólag olyan számokra is működik, amelyek esetén a Fermat-prímteszt csődöt mond.

De vajon mi az oka annak, hogy a Miller-Rabin-prímtesztre nézve egyáltalán nem léteznek univerzális álprímek? Milyen fegyverek állnak Alice és Bob rendelkezésére egy ilyen jellegű kérdés megválaszolásához? Mik azok a csoportok és mivel foglalkozik a csoportelmélet? Mit állít a Lagrange-tétel, és mi köze a Miller-Rabin-prímteszthez? Ebben a részben erről lesz szó…

Figyelem! Ez a rész erőteljesen épít a 18., 20., 22. és 23. részekben felépített alábbi definíciókra, valamint a hozzájuk kapcsolódó tételekre:

18.8. Tétel (A hatványozás azonosságai)

Legyen R egy tetszőleges kommutatív gyűrű, amelynek „szorzás” műveletét jelöljük a szokásos \cdot szimbólummal vagy egymás után írással. Tegyük fel továbbá, hogy ha x a gyűrű valamely eleme, n pedig tetszőleges pozitív egész, akkor az x^n hatványon az alábbi n tényezős „szorzatot” értjük:

x^n=\underbrace{x\cdot x\cdot x\cdot \ldots \cdot x}_{\text{n darab}}

Ekkor tetszőleges a és b gyűrűelemek, valamint tetszőleges n és k pozitív egész számok esetén teljesülnek az alábbi tulajdonságok:

  1. (a\cdot b)^n=a^n\cdot b^n
  2. (a^n)^k=a^{n\cdot k}
  3. a^n\cdot a^k=a^{n+k}
20.6. Definíció (Redukált maradékosztály)

Legyen m\gt 0 egy tetszőleges pozitív egész szám. Ekkor a \Z/m\Z-vel jelölt modulo m maradékosztálygyűrű (lásd a 20.5. Tételt) invertálható elemeit modulo m redukált maradékosztályoknak nevezzük.

22.2. Tétel (Kínai maradéktétel)

Legyen a és b tetszőleges, p\gt 0 és q\gt 0 pedig valamilyen pozitív egész számok. Tegyük fel továbbá, hogy p és q egymáshoz relatív prímek. Ekkor az alábbi kongruenciarendszer megoldható, és a megoldás egyetlen modulo pq maradékosztály lesz:

\begin{aligned}x&\equiv a\pmod p \\ x&\equiv b\pmod q\end{aligned}

Más megfogalmazásban minden, a fenti két kongruenciát egyszerre kielégítő egész szám ugyanabba az egyetlen modulo pq maradékosztályba esik, továbbá ennek a bizonyos maradékosztálynak minden eleme kielégíti a fenti két kongruenciát.

22.8. Tétel (Maradékosztálygyűrűk dekompozíciója)

Legyenek p\gt 0 és q\gt 0 valamilyen pozitív egész számok, továbbá tegyük fel, hogy p és q egymáshoz relatív prímek. Ekkor a 22.7. Tétel szerint értelmezett \Z/p\Z \times \Z/q\Z gyűrű izomorf a \Z/pq\Z maradékosztálygyűrűvel (lásd a 18.6. Definíciót). Azaz:

\Z/p\Z \times \Z/q\Z\simeq \Z/pq\Z

Legyenek a, b és c tetszőleges egész számok, továbbá tegyük fel, hogy az x_1 és x_2 egész számok kielégítik az alábbi kongruenciákat:

\begin{aligned}p\cdot x_1&\equiv 1\pmod q \\ q\cdot x_2&\equiv 1\pmod p\end{aligned}

Ekkor az alábbi f:\Z/p\Z \times \Z/q\Z \to \Z/pq\Z és g:\Z/pq\Z \to \Z/p\Z \times \Z/q\Z leképezések épp egymás megfordításai, továbbá mindketten gyűrűizomorfizmusok a két gyűrű között:

\begin{aligned}f(([a]_p;[b]_q))&=[a\cdot q\cdot x_2 + b\cdot p\cdot x_1]_{pq} \\ g([c]_{pq})&=([c]_p;[c]_q)\end{aligned}

23.7. Definíció (Univerzális álprímek, Carmichael-számok)

Legyen n\gt 1 tetszőleges pozitív, továbbá a egy n-hez relatív prím egész szám, és tegyük fel, hogy n összetett. Amennyiben az [a]_n redukált maradékosztály NEM Fermat-tanú, akkor azt mondjuk, hogy n álprím az a alapra nézve.

Amennyiben a modulo n redukált maradékosztályok között egyáltalán nem létezik Fermat-tanú, akkor n-et univerzális álprímnek vagy Carmichael-számnak nevezzük.

23.9. Definíció (Miller-Rabin-tanú)

Legyen n\gt 1 egy tetszőleges páratlan szám, a pedig tetszőleges egész szám, amely nem többszöröse n-nek, azaz n\nmid a. Képezzük azt az e\geq 1 kitevőt és k\geq 1 páratlan számot, amelyekre teljesül az alábbi:

n-1=2^e\cdot k

Tegyük fel továbbá, hogy az alábbi kongruenciák egyike sem teljesül:

\begin{aligned}a^k&\equiv +1\pmod n \\ a^k&\equiv -1\pmod n \\ a^{2k}&\equiv -1\pmod n \\ a^{4k}&\equiv -1\pmod n \\ &\vdots \\ a^{2^{e-1}\cdot k}&\equiv -1\pmod n\end{aligned}

Ekkor az a egész szám által reprezentált [a]_n maradékosztályt az n egész szám Miller-Rabin-tanújának nevezzük.

Ezek kontextusba helyezése miatt erőteljesen ajánlott elolvasni a 18., 20., 22. és 23. részeket, mivel gyakran hivatkozni fogunk rájuk. A teljes cikksorozat elejét itt találod.

Amikor a 11. részben elkezdtük a számelmélet felépítését, viszonylag hamar eljutottunk arra a felismerésre, hogy bizonyos, az egész számokkal kapcsolatos fogalmakat célszerű absztrakt szinten kezelni. Így jutottunk el a 14. részben a neutrális elem (14.7. Definíció), az inverz (14.9. Definíció) és végül a gyűrű (14.12. Definíció) fogalmához. Ezáltal általános érvényű összefüggéseket tudtunk feltárni, amelyek az ideálok elméletén (18. és 19. rész) keresztül elvezettek minket a számelmélet alaptételével kapcsolatos alapvető fontosságú felismerésekhez. Végül a 20., 21., és 22. részekben az így megszerzett ismereteket alkalmazhattuk az egész számok \Z gyűrűjére. Ezáltal részletesen megismerhettük a napjainkban leggyakrabban használt titkosítási eljárás, az RSA-algoritmus működését.

Azonban az előző részben ismertetett prímtesztelő eljárásokkal kapcsolatban felmerült egy olyan kérdés, amelyet még nem válaszoltunk meg. Nevezetesen: vajon a Miller-Rabin-prímteszt – ellentétben a Fermat-prímteszttel – valóban képes-e kiszűrni az univerzális álprímeket (23.7. Definíció)?

Ahhoz, hogy ezt a kérdést megválaszolhassuk, meg kell ismerkednünk az absztrakt algebra egyik fontos fegyverével, az úgynevezett csoportelmélettel.

A csoportelmélet megszületése

A csoportelmélet keletkezése a XIX. század első felére tehető Niels Henrik Abel és Évariste Galois úttörő munkásságának köszönhetően. Munkájukat az akkori matematika egyik központi témája inspirálta, amely arról szólt, hogy különféle típusú egyenleteket hogyan lehet megoldani. A kor matematikusai az egyes egyenlettípusokra olyan megoldóképleteket kerestek, amelyekben csak a négy alapművelet és az úgynevezett gyökvonás művelete szerepelhet, méghozzá véges sokszor. Egy ilyen általános megoldóképlet azért jó dolog, mert a segítségével bárki meg tud oldani bármilyen, az adott típusba tartozó egyenletet. Egyszerűen csak annyi a dolga, hogy a képletben szereplő betűk helyére beírja a konkrét egyenlet paramétereit, a megfelelő sorrendben elvégzi a képlet által leírt műveletsorozatot, és varázslatos módon megkapja a végeredményt.

Tekintsük például a legegyszerűbb egyenlettípust, az úgynevezett elsőfokú egyenleteket. Egy ilyen egyenlet általános formája a következőképpen néz ki:

ax+b=0

Itt a\neq 0 és b valamilyen konkrét számok, az x pedig azt az ismeretlen számot (vagy esetleg számokat) jelöli, amelyet (vagy amelyeket) keresünk. Minden olyan egyenletet, amely ilyen alakra hozható, elsőfokú egyenletnek nevezünk. Az „elsőfokú” elnevezés itt azt fejezi ki, hogy egy ilyen egyenletben az x ismeretlen az első hatványon szerepel. Az elsőfokú egyenlet általános megoldóképlete a következő:

x=\frac{-b}{a}

Ha például valamilyen konkrét számítási feladat kapcsán mondjuk a 3x-6=0 egyenletet kell megoldanunk, akkor egy ilyen megoldóképlettel a zsebünkben könnyű dolgunk van. Elsőként meg kell határoznunk, hogy az egyenletben szereplő számok az egyenlet általános formájában melyik betűknek felelnek meg. Itt például a=3 és b=-6. Ezután már csak be kell helyettesítenünk a megoldóképletbe ezeket a számokat, és meg is kapjuk a végeredményt:

x=\frac{-b}{a}=\frac{-(-6)}{3}=\frac{6}{3}=2

Valóban, ha az eredeti 3x-6=0 egyenletbe az ismeretlen helyére behelyettesítjük az x=2 megoldást, akkor tényleg fennáll az egyenlőség a két oldal között. Továbbá a megoldóképlet implicit módon azt is meghatározza, hogy összesen hány megoldás van. Elsőfokú egyenletek esetén mindig egyetlen megoldás létezik.

Egy ennél bonyolultabb egyenlettípust alkotnak az úgynevezett másodfokú egyenletek. Ezek általános alakja a következő:

ax^2+bx+c=0

Egy másodfokú egyenletben tehát már az ismeretlen mennyiség második hatványa is szerepel. Anélkül, hogy belemennénk az indoklás részleteibe, megadjuk a másodfokú egyenlet megoldóképletét:

\begin{aligned}x_1&=\frac{-b+\sqrt{b^2-4ac}}{2a} \\ x_2&=\frac{-b-\sqrt{b^2-4ac}}{2a}\end{aligned}

A megoldások száma tehát ebben az esetben 2, 1 vagy 0 lesz attól függően, hogy a gyökjel alatt pozitív, 0 vagy negatív szám szerepel. Tekintsük például az alábbi másodfokú egyenletet:

x^2+2x-3=0

Itt ugye a=1, b=2 és c=-3. Ezeket behelyettesítve a megoldóképletbe az x_1=-3 és az x_2=1 megoldásokat kapjuk.

Egyenletek egy még bonyolultabb típusait képviselik az úgynevezett harmad- és negyedfokú egyenletek. Ezek általános alakjai a következők:

\begin{aligned}ax^3+bx^2+cx+d&=0 \\ ax^4+bx^3+cx^2+dx+e&=0\end{aligned}

A harmad- és negyedfokú egyenletek megoldóképleteit a XVI. század elején fedezték fel itáliai matematikusok, amelyekről itt és itt olvashatunk bővebben. Ezek a megoldóképletek azonban már annyira bonyolultak, hogy a gyakorlatban az ilyen típusú egyenleteket – amennyiben szükséges – közelítő módszerekkel oldjuk meg. A matematikusokat azonban ez egyáltalán nem zavarta abban, hogy kitartóan keressék az ötöd- és magasabbfokú egyenletek megoldóképleteit.

A XIX. század elején még mindig nem sikerült ezen a téren semmi eredményt felmutatni, mígnem Niels Henrik Abel 1824-ben egy meglepő cikket publikált. Ebben igazolta, hogy az ötöd- és magasabbfokú egyenletekhez nem létezik általánosan működő megoldóképlet. Ez persze nem azt jelenti, hogy megoldás sem létezik, hanem azt, hogy a megoldások nem fejezhetők ki az egyenlet paramétereinek a segítségével egy véges sok műveletet tartalmazó zárt képletben. Nem sokkal ezután Évariste Galois általánosságban is megadta az egyenletek algebrai megoldhatóságának kritériumait. Ezt a korszakalkotó munkát manapság Galois-elmélet néven ismerjük, amely azóta a számelmélet egy jelentős eszközévé vált.

Többek között a Galois-elmélet vezetett el a csoport fogalmának megalkotásához. Időközben aztán kiderült, hogy ez a fogalom rengeteg más matematikai területen is alapvető szerepet játszik. Például az úgynevezett szimmetriacsoportok segítségével vizsgálni lehet különböző bonyolult alakzatok szimmetriáit, amelyek sokmindent elárulnak magukról az alakzatokról is. Ennek fontos alkalmazásai vannak többek között a kémiában – kristályrácsok szerkezetének elmélete – és a fizikában – a téridő szimmetriáinak vizsgálata. Később Félix Klein a geometriának is alapvető eszközévé tette a csoportokat, de fontos szerepet játszanak a matematika egyik legabsztraktabb területén, az algebrai topológiában is.

Minthogy ennyire különböző területeken jelennek meg, a XIX. század végére kiderült, hogy a csoportokat egyszerre, egymáshoz való viszonyaikban célszerű vizsgálni. Megszületett az absztrakt csoport fogalma, és az lett a feladat, hogy az általános csoportoknak minél jobban feltárjuk a szerkezetét, és olyan struktúratételeket bizonyítsunk, amelyek alapján az alkalmazásokban felmerülő kérdésekre válaszolni lehet.

Például az olyan kérdésekre is, hogy vajon a Miller-Rabin-prímteszt képes-e kiszűrni minden univerzális álprímet? Ismerkedjünk meg ezért most a csoportelmélet néhány alapvető fogalmával és összefüggésével.

Csoportelméleti gyorstalpaló

A 14.12. Definícióban megismerkedtünk a gyűrű fogalmával, amely eddigi vizsgálataink tárgyát képezte. Egy gyűrű tulajdonképpen nem más, mint egy halmaz, amelyen értelmezve van két művelet, és ezek a műveletek teljesítenek néhány egyszerű követelményt, amelyeket gyűrűaxiómáknak nevezünk.

A csoportok a gyűrűkhöz hasonló algebrai struktúrák, azonban alaphalmazukon nem kettő, hanem csak egy művelet van értelmezve. Az alábbi definíció tartalmazza azokat a követelményeket – a csoportaxiómákat –, amelyeknek e művelet meg kell feleljen.

24.1. Definíció (Félcsoport, csoport):

Tegyük fel, hogy adva van egy valamilyen G halmaz, amelyen értelmezve van egy kétváltozós művelet. Nevezzük ezt a műveletet szorzásnak és jelöljük \cdot-tal, vagy egymás után írással. Például egy a és egy b elem szorzatát jelöljük a\cdot b-vel vagy ab-vel.

Az így kapott (G,\cdot ) algebrai struktúrát félcsoportnak nevezzük, amennyiben az említett művelet asszociatív. Azaz tetszőleges a, b és c elemek esetén teljesül az alábbi:

(a\cdot b)\cdot c = a\cdot (b\cdot c)

Csoportnak nevezzük az olyan félcsoportokat, amelyek esetén az asszociativitáson kívül a műveletre nézve létezik neutrális elem is (14.7. Definíció), továbbá a művelet invertálható (14.9. Definíció). Egy csoport esetén a neutrális elemet általában e-vel vagy 1-gyel szoktuk jelölni, és ilyenkor egységelemről beszélünk. Egy a elem inverzét a^{-1}-gyel szoktuk jelölni. Tetszőleges a elem esetén teljesülnek tehát az alábbiak:

\begin{aligned}a\cdot e &= e\cdot a = a \\ a\cdot a^{-1} &= a^{-1}\cdot a = e\end{aligned}

Amennyiben a művelet a fentieken felül még kommutatív is, úgy Abel-csoportról vagy kommutatív csoportról beszélünk. Abel-csoportok esetén a csoportműveletet tipikusan a + szimbólummal, a neutrális elemet 0-val, egy a elem inverzét pedig -a-val szoktuk jelölni. Ilyenkor a neutrális elemet nullelemnek, az a elem inverzét pedig a ellentettjének nevezzük.

Például az egész számok \Z halmaza Abel-csoportot alkot a szokásos összeadásra nézve. Ebben a csoportban a neutrális elem a 0 egész szám, egy a egész szám inverze pedig az ellentettje, azaz -a, hiszen őket összeadva épp a neutrális elemet, azaz a 0 egész számot kapjuk eredményül.

A \Z halmaz a szorzásra nézve viszont nem alkot csoportot. Igaz ugyan, hogy a szorzásra nézve létezik neutrális elem – az 1 egész szám –, azonban rajta és a -1-en kívül más egész számnak nem létezik inverze. A csak az 1-ből és a -1-ből álló kételemű halmaz viszont már csoportot alkot a szorzásra nézve is.

A most következő tétel egy fontos összefüggést mond ki két elem inverzei és a szorzatuk inverze között. A tételt teljes általánosságban, azaz nem kimondottan csoportokra fogalmazzuk meg.

24.2. Tétel (Szorzat inverze):

Legyen H egy tetszőleges halmaz, amelyen értelmezve van egy *-gal jelölt asszociatív művelet, és tegyük fel, hogy létezik H-ban neutrális elem (14.7. Definíció) erre a műveletre nézve. Legyenek továbbá x és y a H halmaz két olyan eleme, amelyek invertálhatók (14.9. Definíció) a * műveletre nézve. Jelöljük ezek inverzeit rendre x^{-1}-gyel és y^{-1}-gyel. Ekkor teljesül az alábbi azonosság:

(x*y)^{-1}=y^{-1}*x^{-1}

Ha x és y felcserélhetők, azaz x*y=y*x, akkor teljesül az alábbi azonosság is:

(x*y)^{-1}=x^{-1}*y^{-1}

Bizonyítás:

Ha e-vel jelöljük a * művelet neutrális elemét, akkor egyrészt:

(x*y)*(y^{-1}*x^{-1})=x*(\underbrace{y*y^{-1}}_{=e})*x^{-1}=x*x^{-1}=e

Másrészt:

(y^{-1}*x^{-1})*(x*y)=y^{-1}*(\underbrace{x^{-1}*x}_{=e})*y=y^{-1}*y=e

Azaz a 14.9. Definíció alapján (x*y) és y^{-1}*x^{-1} valóban egymás inverzei. Ha x és y felcserélhetők, akkor pedig nyilván (x*y)^{-1}=(y*x)^{-1}=x^{-1}*y^{-1} is igaz.

Az imént megismert csoport és félcsoport fogalmának segítségével az alábbi definícióban egyrészt jóval egyszerűbb módon megadhatjuk a 14.12. Definícióban szereplő gyűrűaxiómákat. Másrészt újabb fontos, gyűrűkkel kapcsolatos csoportelméleti fogalmakkal is megismerkedünk.

24.3. Definíció (Gyűrű additív és multiplikatív csoportja):

A 14.12. Definíció-ban szereplő gyűrűaxiómák a 24.1. Definícióban ismertetett félcsoport és csoport fogalmának segítségével átfogalmazhatók. Eszerint tegyük fel, hogy adva van egy R halmaz, amelyen értelmezve van egy +-szal és egy \cdot-tal jelölt kétváltozós művelet. Az (R,+,\cdot) algebrai struktúrát gyűrűnek nevezzük, ha teljesülnek az alábbiak:

  1. Az R halmaz a + művelettel Abel-csoportot alkot.
  2. Az R halmaz a \cdot művelettel félcsoportot alkot.

Az 1. pontban szereplő (R,+) Abel-csoportot az R gyűrű additív csoportjának nevezzük és R^+-szal jelöljük. Amennyiben az R gyűrű egységelemes, akkor vannak olyan elemei, amelyeknek a \cdot műveletre nézve is létezik inverze – az egységelem és ellentettje például mindenképpen ilyen. Ezeknek az invertálható elemeknek a halmaza – amely tehát R-nek egy nemüres részhalmaza – a \cdot művelettel szintén csoportot alkot, amelyet az R gyűrű multiplikatív csoportjának nevezzük és R^{\times}-tel jelöljük.

Megjegyzés:

A 24.1. Definíció alapján könnyen leellenőrizhető, hogy az R^{\times} halmaz valóban csoportot alkot az R gyűrű \cdot műveletével.

Előszöris R^{\times} zárt a \cdot műveletre nézve. Legyen ugyanis a és b az R gyűrű két invertálható eleme – azaz a\in R^{\times} és b\in R^{\times}. Ekkor az ab szorzat is invertálható – azaz ab\in R^{\times} –, méghozzá a 24.2. Tétel alapján:

(ab)^{-1}=b^{-1}a^{-1}

Más szavakkal tehát az R halmazon értelmezett \cdot művelet algebrai értelemben művelet az R-nél szűkebb R^{\times} halmazon is (lásd a 11.3. Definíciót). Így ha a \cdot művelet R-en asszociatív volt, akkor nyilván R^{\times}-en is az.

Másodszor R^{\times}-ben létezik neutrális elem, méghozzá az R gyűrű egységeleme. Neki ugyanis nyilván létezik R-beli inverze a \cdot műveletre nézve: önmaga.

Harmadszor minden R^{\times}-beli elemnek az inverze szintén R^{\times}-ben van – azaz R^{\times} zárt az R-beli inverzképzésre is. Tegyük fel ugyanis, hogy egy a\in R^{\times} elem R-beli inverze a^{-1}, azaz aa^{-1}=1 és a^{-1}a=1. Mivel 1 benne van R^{\times}-ben, ezért a-nak az R^{\times}-beli inverze szintén csak a^{-1} lehet, hiszen a 14.10. Tétel alapján az inverzképzés egyértelmű.

Az R^{\times} halmaz tehát valóban csoportot alkot az R gyűrű \cdot műveletével.

Végül felhívjuk a figyelmet, hogy amennyiben R kommutatív és egységelemes, akkor érvényes a 16.5. Tétel. Ez alapján R valamely eleme akkor és csak akkor invertálható, ha egység. Az egységek ugyanis ilyenkor épp az egységelem osztói, ami ugye a 16.1. Definíció alapján azt jelenti, hogy létezik hozzájuk olyan elem, amellyel őket összeszorozva az egységelemet kapjuk eredényül. Egy kommutatív, egységelemes R gyűrű multiplikatív csoportja tehát R egységeiből áll. Speciálisan ha R test, akkor a 16.3. Definíció utáni megjegyzés alapján R^{\times} a nullelemen kívül minden R-beli elemet tartalmaz.

Az iménti megjegyzés alapján tehát egy kommutatív, egységelemes gyűrű invertálható elemei csoportot alkotnak a gyűrű szorzására nézve. Számunkra ebben a részben főként a 20.5. Tételben definiált modulo n maradékosztálygyűrű multiplikatív csoportja lesz érdekes. Ez a 20.6. Definíció alapján épp a redukált maradékosztályokból áll.

Például a \Z/10\Z maradékosztálygyűrű multiplikatív csoportját (\Z/10\Z)^{\times}-vel jelöljük, és az alábbi 4 elemből áll:

(\Z/10\Z)^{\times}=\{[1]_{10}; [3]_{10}; [7]_{10}; [9]_{10}\}

A 20.5. Tételben definiált maradékosztályok közötti szorzás műveleti táblája így néz ki ebben a csoportban:

\begin{array}{c|cccc}\odot & [1]_{10} & [3]_{10} & [7]_{10} & [9]_{10} \\ \hline [1]_{10} & [1]_{10} & [3]_{10} & [7]_{10} & [9]_{10} \\ [3]_{10} & [3]_{10} & [9]_{10} & [1]_{10} & [7]_{10} \\ [7]_{10} & [7]_{10} & [1]_{10} & [9]_{10} & [3]_{10} \\ [9]_{10} & [9]_{10} & [7]_{10} & [3]_{10} & [1]_{10} \end{array}

Látható, hogy valóban minden elemnek létezik inverze. Például a [7]_{10} maradékosztály inverze a [3]_{10} maradékosztály, hiszen az ő szorzatuk az [1]_{10} maradékosztály, amely a (\Z/10\Z)^{\times} csoport neutrális eleme.

Részcsoportok

A 18.14. Definícióban megismerkedtünk a részgyűrű fogalmával. Ott arról volt szó, hogy egy gyűrű műveleteit az eredeti alaphalmaz helyett annak egy részhalmazára is leszűkíthetjük. Példaként a páros számok 2\Z halmazát hoztuk fel. A szokásos összeadás és szorzás ugye a teljes \Z halmazon van értelmezve. Azonban ez a két művelet „nem vezet ki” az ennél szűkebb 2\Z halmazból sem, hiszen bármely két páros szám összege és szorzata is páros. Így a 2\Z halmaz az eredeti \Z gyűrű műveleteinek szűkített változataival maga is gyűrűt alkot, azaz részgyűrűje az eredeti \Z gyűrűnek.

Hasonló értelemben vett részstruktúrákról természetesen beszélhetünk csoportok esetén is. Itt is ugyanarról van szó azzal a különbséggel, hogy egy csoportban csak egy műveletünk van.

24.4. Definíció (Részcsoport):

Ha egy G csoport valamely H részhalmaza maga is csoport a G műveletére nézve, akkor azt mondjuk, hogy H részcsoport G-ben. Ezt így jelöljük: H\leq G.

Ha H részcsoport G-ben, de H\neq G, akkor azt mondjuk, hogy H valódi részcsoport G-ben. Ezt így jelöljük: H\lt G.

Megjegyzés:

A 19.6. Tételben igazoltuk, hogy a \sube szimbólummal jelölt tartalmazási reláció egy részbenrendezés bármilyen halmazrendszer elemei között, azaz reflexív, antiszimmetrikus és tranzitív. Továbbá azt is igazoltuk, hogy a \sub szigorú tartalmazási reláció ezek közül csak a tranzitivitást teljesíti.

Minthogy egy G csoport bármely H részcsoportja tulajdonképpen G-nek részhalmaza, továbbá örökli a G műveletét, ezért ezek a tulajdonságok természetesen a \leq szimbólummal jelölt „részcsoportjának lenni”-relációra is érvényesek.

Például a fentebb már szereplő (\Z/10\Z)^{\times} multiplikatív csoport esetén az alábbi kételemű halmaz egy valódi részcsoportot alkot:

G=\{[1]_{10}; [9]_{10}\}

Ha a (\Z/10\Z)^{\times} szorzótáblájából kihagyjuk a két-két középső sort és oszlopot, akkor megkapjuk ennek a részcsoportnak a szorzótábláját:

\begin{array}{c|cc}\odot & [1]_{10} & [9]_{10} \\ \hline [1]_{10} & [1]_{10} & [9]_{10} \\ [9]_{10} & [9]_{10} & [1]_{10} \end{array}

Mivel csupán kételemű halmazról van szó, ezért az Olvasó maga is könnyen leellenőrizheti, hogy valóban teljesülnek a 24.1. Definícióban szereplő csoportaxiómák.

Ezt azonban nem kell minden olyan alkalommal megtenni, amikor egy részhalmazról el szeretnénk dönteni, hogy részcsoport-e vagy sem. Az alábbi tétel a 18.15. Tétel mintájára egy sok esetben a csoportaxiómáknál könnyebben ellenőrizhető feltételrendszert ad ehhez. A bizonyítás szinte szóról szóra megegyezik a 18.15. Tétel bizonyításával.

24.5. Tétel:

Egy tetszőleges G csoport valamely H részhalmaza akkor és csak akkor részcsoport G-ben, ha teljesülnek az alábbi feltételek:

  1. H zárt a G csoport műveletére.
  2. H tartalmazza a G csoport egységelemét.
  3. H zárt a G-beli inverzképzésre.

Bizonyítás:

Tegyük fel, hogy H részcsoport G-ben. Ekkor a műveleti zártság – azaz az 1. tulajdonság – nyilvánvalóan teljesül, máskülönben H nem lenne csoport a G műveletére nézve, és így részcsoport sem lehetne G-ben.

Mivel H-nak létezik egységeleme – hiszen maga is csoport –, ezért a 2. tulajdonsághoz azt kell megmutatni, hogy ez az egységelem megegyezik G egységelemével. Jelöljük H egységelemét e_H-val, G egységelemét pedig e_G-vel, és tegyük fel indirekt, hogy ez a kettő nem ugyanaz. Ha a kettő nem ugyanaz, akkor az sem mindegy, hogy melyik csoportban beszélünk inverzképzésről. Jelölje most {e_H}^{-1} az e_H elem G-beli inverzét. Őket összeszorozva tehát a G csoport egységelemét kell kapjuk, azaz:

e_H\cdot {e_H}^{-1}=e_G

Mivel e_H a H csoport egységeleme, ezért nyilvánvalóan igaz az alábbi:

e_H\cdot e_H=e_H

Végül, mivel e_G a G csoport egységeleme, ezért az alábbi is teljesül:

e_H\cdot e_G=e_H

Mivel H csoport, így a csoportművelet asszociativitása miatt:

(e_H\cdot e_H)\cdot {e_H}^{-1}=e_H\cdot (e_H\cdot {e_H}^{-1})

A baloldalt kifejtve ezt kapjuk:

\underbrace{(e_H\cdot e_H)}_{=e_H}\cdot {e_H}^{-1}=e_H\cdot {e_H}^{-1}=e_G

A jobboldalt kifejtve pedig ezt:

e_H\cdot \underbrace{(e_H\cdot {e_H}^{-1})}_{=e_G}=e_H\cdot e_G=e_H

Ez a kettő eredmény viszont a fentebb már említett asszociativitás miatt indirekt feltételezésünkkel ellentétben mégis meg kell egyezzen, így valóban e_G=e_H.

Végül az inverzképzésre való zártság – azaz a 3. tulajdonság – igazolásához képezzük a H csoport valamely a elemének inverzét mindkét csoportban, és megmutatjuk, hogy ezek valójában megegyeznek. A H-beli inverzet jelöljük x_H-val, míg a G-beli inverzet x_G-vel. Az a elemet a G-beli inverzével összeszorozva a G csoport egységelemét kell kapnunk, azaz:

a\cdot x_G=e_G

Ugyanakkor az a elemet a H-beli inverzével összeszorozva a H csoport egységelemét kell kapnunk, amiről azonban már láttuk, hogy megegyezik a G csoport egységelemével. Azaz:

a\cdot x_H=e_H=e_G

Minthogy a G-beli inverzképzés a 14.10. Tétel alapján egyértelmű, ezért szükségképpen x_H=x_G. Azaz a H csoport valóban zárt a G-beli inverzképzésre.

Visszafelé: Most azt kell megmutatnunk, hogy amennyiben teljesül mind a 3 tulajdonság, úgy H részcsoport G-ben. A G csoport művelete az 1. tulajdonság alapján nem vezet ki H-ból, így az algebrai értelemben művelet ezen a szűkebb halmazon is (lásd a 11.3. Definíciót). Továbbá a 2. és 3. tulajdonság miatt létezik egységelem, és minden elemnek létezik inverze is H-ban. Így a 24.1. Definíció szerinti csoportaxiómákból már csak a művelet asszociativitását kell igazolnunk. Ezeket azonban H megörökli a G-től a művelettel együtt. Így tehát H valóban részcsoport G-ben.

Lagrange tétele

Ebben a szakaszban egy kulcsfontosságú tételt fogunk igazolni, amely egy tetszőleges véges csoport illetve annak részcsoportjainak elemszáma között mond ki egy fontos összefüggést. Először azonban tisztázzuk, hogy pontosan mit értünk egy csoport elemszámán.

24.6. Definíció (Csoport rendje):

Egy G csoport rendje alatt a benne lévő elemek számát értjük. Pontosabban fogalmazva ha G csak véges sok elemet tartalmaz, és elemeinek száma n, akkor azt mondjuk, hogy G véges, és rendje n. Ezt így jelöljük: |G|=n. Ezzel szemben ha G végtelen sok elemet tartalmaz, akkor végtelen rendű csoportról beszélünk. Ezt így jelöljük: |G|=\infty.

Mivel egy csoport részcsoportjai a 24.4. Definíció értelmében maguk is csoportok, ezért egy részcsoport rendje alatt szintén a fenti értelemben vett rendet értjük.

Most bevezetünk egy fontos relációt egy adott G csoport elemei között, amely relációt G egy adott részcsoportja segítségével határozunk meg. Továbbá igazoljuk, hogy ez egy ekvivalenciareláció (13.4. Definíció), amely tehát ekvivalencia-osztályokra bontja a G csoportot. Ez az ekvivalenciareláció némileg speciálisabb formában korábban már szerepelt a 18.20. Definícióban, ahol őt ideál szerinti kongruenciának hívtuk. Erre a tétel utáni megjegyzésben bővebben is kitérünk.

24.7. Tétel (Mellékosztályok):

Legyen G tetszőleges csoport, H pedig valamilyen részcsoport G-ben. Definiáljunk egy \sim szimbólummal jelölt relációt a G csoport elemei között a következőképpen: a\sim b akkor és csak akkor, ha a^{-1}b\in H.

Ekkor a \sim reláció egy ekvivalenciareláció a G csoport elemei között. Az ehhez tartozó ekvivalencia-osztályokat a G csoport H részcsoportja szerinti baloldali mellékosztályoknak nevezzük. Ha g egy tetszőleges elem a G csoportban, akkor a g elemet tartalmazó H szerinti baloldali mellékosztály épp a 18.19. Definícióban bevezetett komplexusszorzással képzett gH halmaz lesz.

Ehhez hasonlóan, ha az a\sim b relációt úgy definiáljuk, hogy akkor és csak akkor teljesüljön, ha ba^{-1}\in H, akkor ugyanígy egy ekvivalenciarelációt kapunk. Ebben az esetben az ekvivalencia-osztályokat a H részcsoport szerinti jobboldali mellékosztályoknak nevezzük, a g elemet tartalmazó jobboldali mellékosztály pedig a Hg halmaz lesz.

Bizonyítás:

A 13.4. Definíció alapján azt kell tehát bizonyítani, hogy a \sim szimbólummal jelölt reláció reflexív (12.8. Definíció), tranzitív (12.10. Definíció) és szimmetrikus (13.3. Definíció). Az alábbiakban legyenek a, b és c a G csoport tetszőleges elemei, az egységelemet pedig jelöljük e-vel. A bizonyítás során végig arra fogunk támaszkodni, hogy H részcsoport G-ben.

Mivel nyilván a^{-1}a=e teljesül, és a G csoport egységeleme a 24.5. Tétel 2. pontja alapján benne van a H részcsoportban, ezért fennáll az a\sim a reláció, így az reflexív.

Ha a^{-1}b és b^{-1}c benne vannak H-ban, akkor a 24.5. Tétel 1. pontja alapján az ő szorzatuk is benne van H-ban. Az ő szorzatuk viszont épp az a^{-1}c elem, hiszen:

a^{-1}\cdot \underbrace{b\cdot b^{-1}}_{=e}\cdot c=a^{-1}ec=a^{-1}c

Így tehát az a\sim b és b\sim c relációkból következik az a\sim c reláció, azaz teljesül a tranzitivitás is.

Végül ha a^{-1}b benne van H-ban, akkor a 24.5. Tétel 3. pontja alapján az ő inverze, is benne van H-ban. Az ő inverze viszont a 24.2. Tétel szerint épp b^{-1}a, hiszen:

(a^{-1}b)^{-1}=b^{-1}(a^{-1})^{-1}=b^{-1}a

Vagyis a\sim b-ből következik b\sim a, ami épp a szimmetriát jelenti.

A \sim reláció tehát valóban egy ekvivalenciareláció, amely a G csoport alaphalmazát ekvivalencia-osztályokra bontja. Ezek lesznek a H szerinti baloldali mellékosztályok. A g elemet tartalmazó mellékosztály pontosan azokból az x elemekből fog állni, amelyekre teljesül a g\sim x reláció. A tétel szövege alapján ez pontosan azt jelenti, hogy a g^{-1}x szorzat benne van H-ban. Ez viszont a 18.19. Definícióban bevezetett komplexusműveletek nyelvén pontosan azt jelenti, hogy x benne van a gH halmazban.

A tétel jobboldali mellékosztályokra vonatkozó állítása pontosan ugyanezzel a gondolatmenettel igazolható, csak ott a szorzásokat fordított sorrendben kell felírni.

Megjegyzés:

A figyelmes Olvasó észreveheti, hogy ez a bizonyítás szinte szó szerint megegyezik a 18.21. Tétel bizonyításával. A különbség pusztán annyi, hogy abban a tételben a G csoport szerepét az ott szereplő R gyűrű additív csoportja, míg a H részcsoport szerepét az ott szereplő I ideál, mint részgyűrű, végül a \sim relációt az I ideál szerinti kongruenciareláció tölti be. Az I szerinti maradékosztályok tehát tulajdonképpen az R gyűrű additív csoportjának I szerinti mellékosztályai.

Ebben az esetben azonban nincs értelme külön bal- illetve jobboldali mellékosztályokról beszélnünk, hiszen az R gyűrűn értelmezett + művelet kommutativitása miatt ezek nyilván megegyeznek. Egy általános csoport esetén azonban nem követeljük meg a csoportművelet kommutativitását, ezért ilyenkor a jobb- és baloldali mellékosztályok is általában különböző halmazok lesznek, azaz általában gH\neq Hg.

A 18.21. Tételben definiált maradékosztályokhoz – vagy speciálisan az egész számok maradékosztályaihoz – hasonlóan a mellékosztályok esetén is beszélhetünk reprezentánselemekről. Tegyük fel például, hogy egy H szerinti baloldali (vagy jobboldali) mellékosztályból a g elemet választottuk reprezentánselemnek. Ekkor egyrészt az iménti tétel alapján az adott mellékosztályt, mint halmazt gH (vagy jobboldali mellékosztály esetén Hg) alakban tudjuk leírni. Másrészt pedig tetszőleges a csoportelemről könnyen eldönthető, hogy g-vel azonos mellékosztályban van-e, azaz teljesül-e a tételben szereplő g\sim a reláció. Ehhez csak azt kell megvizsgálni, hogy a g^{-1}a (vagy jobboldali mellékosztály esetén az ag^{-1}) szorzat benne van-e a H részcsoportban.

Mostmár megfogalmazhatjuk azt a véges csoportok részcsoportjainak elemszámára vonatkozó fontos összefüggést, amely kulcsfontosságú lesz annak igazolásához, miszerint a Miller-Rabin-prímtesztre nézve nem léteznek univerzális álprímek. Ez az összefüggés Joseph Louis Lagrange olasz születésű francia matematikustól származik, és igen fontos a matematika egyéb területein is.

24.8. Tétel (Lagrange tétele):

Legyen G tetszőleges véges csoport, H pedig tetszőleges részcsoport G-ben. Ekkor a H részcsoport rendje osztója G rendjének, azaz teljesül az alábbi oszthatóság:

|H|\ |\ |G|

Azaz létezik olyan egész szám, amellyel H rendjét megszorozva épp G rendjét kapjuk. Ezt az egész számot a H részcsoport G-beli indexének nevezzük, és |G:H|-val jelöljük. Azaz teljesül az alábbi összefüggés:

|G|=|G:H|\cdot |H|

Bizonyítás:

A bizonyításban a 24.7. Tételben definiált baloldali mellékosztályokat fogjuk használni, de értelemszerűen ugyanígy használhatnánk a jobboldali mellékosztályokat is.

Az említett tételben definiált \sim reláció egy ekvivalenciareláció, melynek ekvivalencia-osztályai a H szerinti baloldali mellékosztályok. Ezek az ekvivalenciarelációkról szóló 13.5. Tétel alapján G egy partícióját alkotják. Azaz semelyik két baloldali mellékosztálynak nincs közös eleme, és uniójuk a teljes G. Ez az elrendezés látható az alábbi ábrán:

Baloldali mellékosztályok partíciója
Baloldali mellékosztályok partíciója

Tekintsük most a G csoportnak egy tetszőleges H szerinti baloldali mellékosztályát, és válasszunk ki belőle egy tetszőleges g elemet, amelyet reprezentánselemként fogunk használni a továbbiakban. A kérdéses mellékosztály tehát a gH halmaz lesz. Most egy kölcsönösen egyértelmű megfeleltetést fogunk létesíteni a gH mellékosztály és a H részcsoport elemei között.

A 24.7. Tétel illetve a hozzá tartozó megjegyzés alapján a gH mellékosztály tetszőleges x eleme esetén a g^{-1}x szorzat a H részcsoportnak egy eleme. Definiáljunk tehát egy f:gH\to H függvényt a következőképpen:

f(x)=g^{-1}x

Azt kell megmutatni, hogy f kölcsönösen egyértelmű megfeleltetés gH és H között. Ez az alábbi két dolgot jelenti:

  1. Tetszőleges x\in gH és y\in gH esetén f(x)=f(y) akkor és csak akkor, ha x=y. Azaz az f függvény H minden elemét legfeljebb egy gH-beli elemhez rendeli hozzá.
  2. Tetszőleges h\in H-hoz létezik olyan x\in gH, amelyre f(x)=h teljesül. Azaz az f függvény H minden elemét legalább egy gH-beli elemhez rendeli hozzá.

Nézzük az 1. állítást! Ha x=y, akkor nyilván teljesül az f(x)=f(y) egyenlőség, hiszen:

f(x)=g^{-1}x=g^{-1}y=f(y)

Visszafelé: ha f(x)=f(y), akkor az azt jelenti, hogy teljesül az alábbi egyenlőség:

g^{-1}x=g^{-1}y

Szorozzuk meg mindkét oldalt balról g-vel (itt e-vel jelöltük a G csoport egységelemét):

\underbrace{gg^{-1}}_{=e}\cdot x=\underbrace{gg^{-1}}_{=e}\cdot y

Ez viszont épp a kívánt x=y egyenlőség.

Most nézzük a 2. állítást! Keresnünk kell tehát egy olyan x elemet a gH mellékosztályban, amelyhez az f függvény épp a H részcsoport h elemét rendeli hozzá. Keressük tehát az alábbi egyenlet megoldását:

\underbrace{g^{-1}x}_{=f(x)}=h

Szorozzuk meg mindkét oldalt balról g-vel (itt e-vel jelöltük a G csoport egységelemét):

\underbrace{gg^{-1}}_{=e}\cdot x=gh

A baloldalról az egységelem elhagyható, így végülis a keresett x előállításának képletét kapjuk: x=gh.

Összefoglalva tehát a fenti f függvény mintájára kölcsönösen egyértelmű megfeleltetés létesíthető a H részcsoport, és bármely H szerinti baloldali mellékosztály között. Néhány mellékosztály esetére ez látható az alábbi ábrán:

Részcsoport és mellékosztályai
Részcsoport és mellékosztályai

Ez azt jelenti, hogy bármely H szerinti baloldali mellékosztálynak pontosan ugyanannyi eleme van, mint magának H-nak. Ha tehát H rendjét megszorozzuk a baloldali mellékosztályok számával, akkor épp G rendjét kapjuk eredményül, hiszen a baloldali mellékosztályok G egy partícióját alkotják. Más szavakkal találtunk egy olyan egész számot – a H szerinti baloldali mellékosztályok számát –, amellyel megszorozva H rendjét épp G rendjét kapjuk. Az oszthatóság 16.1. Definíciója alapján ez épp azt jelenti, hogy |H| osztója |G|-nek.

Megjegyzés:

A 24.7. Tétel utáni megjegyzésben megemlítettük, hogy egy G csoportnak egy H részcsoportja szerinti bal- illetve jobboldali mellékosztályai általában nem azonos halmazok. Azaz ha g a G csoport egy eleme, akkor általában gH\neq Hg. Azonban a Lagrange-tételből azonnal következik, hogy véges G csoport esetén a számuk viszont megegyezik és ez a szám épp |G:H|-val egyezik meg.

Ennél azonban több is igaz. Viszonylag könnyen belátható, hogy a bal- és jobboldali mellékosztályok száma akkor is megegyezik, ha G rendje esetleg végtelen. Sőt, a bal- és jobboldali mellékosztályok között kölcsönösen egyértelmű megfeleltetés létesíthető akkor is, ha történetesen ezek száma is végtelen – és így ebben a végtelen számosságú esetben is „ugyanannyi van belőlük”. Ezek igazolását – illetve az index fogalmának ilyen jellegű általánosítását – azonban most mellőzzük.

Negatív kitevős hatványok

Az előző rész végén felhívtuk Alice és Bob figyelmét arra, hogy nagyon nem szerencsés, ha több – vagy akár az összes – felhasználónak az RSA-kulcsgenerálás során ugyanazokat a prímszámokat, és így ugyanazt a modulust választják. Ezáltal ugyanis egy potenciális támadónak a Bézout-lemma (21.1. Tétel) felhasználásával lehetősége nyílik arra, hogy kizárólag publikusan elérhető információkból – tehát az RSA feltörése nélkül – megfejthessen titkos üzeneteket. Ez abban az esetben lehetséges, ha egy adott felhasználó ugyanazt az x nyílt üzenetet (például egy körlevelet) legalább 2 másik olyan felhasználónak is elküld, akik azonos modulust használnak.

Szinte majdnem biztos ugyanis, hogy e két felhasználó e_1 és e_2 publikus kitevője egymáshoz relatív prím. Azaz kitüntetett közös osztójuk 1, ami a Bézout-lemma alapján az euklidészi algoritmus segítségével hatékonyan meg tudja találni azokat az u és v egész számokat, amelyekre teljesül az alábbi:

u\cdot e_1 + v\cdot e_2=(e_1, e_2)=1

Mármost ha e két felhasználó azonos modulust használ, akkor a nekik küldött y_1 és y_2 kódszövegekből, továbbá a támadó által kiszámított u és v egész számokból a hatványozás azonosságairól szóló 18.8. Tétel valamint a kongruencia tulajdonságairól szóló 20.2. Tétel alapján elvileg könnyedén megkapható az x nyílt üzenet:

(\underbrace{x^{e_1}}_{\equiv y_1})^u\cdot (\underbrace{x^{e_2}}_{\equiv y_2})^v = x^{\overbrace{u\cdot e_1 + v\cdot e_2}^{=1}}\equiv x\pmod m

Megemlítettük ugyanakkor, hogy mivel a kitevőben szereplő e_1 és e_2 számok mindketten pozitívak, ezért u és v közül pontosan az egyik szükségképpen negatív, és így az említett két tételt nem használhattuk volna.

Ezért ebben a szakaszban kiterjesztjük a hatványozás fogalmát csak pozitív kitevőkről tetszőleges egész kitevőkre is. Ez olyan esetekben tehető meg, amikor a művelet – amelynek ugye a többszöri elvégzését értjük a hatványozás alatt – rendelkezik neutrális elemmel és invertálható. Az alábbi definícióban ezt teljes általánosságban fogalmazzuk meg.

24.9. Definíció (Egész kitevős hatvány):

Legyen H tetszőleges halmaz, amelyen értelmezve van egy *-gal jelölt asszociatív művelet. Ha x a H halmaz valamely eleme, n pedig tetszőleges pozitív egész, akkor az x^n hatványon az alábbi kifejezést értjük:

x^n=\underbrace{x*x*x*\ldots *x}_{\text{n darab}}

Tegyük fel, hogy a * műveletre nézve létezik neutrális elem (14.7. Definíció), amelyet jelöljünk e-vel. Ekkor az x^0 hatványon az alábbit értjük:

x^0=e

Végül tegyük fel, hogy az x elem invertálható (14.9. Definíció), és jelöljük az ő (kétoldali) inverzét x^{-1}-gyel. Ekkor az x^{-n} hatványon az alábbit értjük:

x^{-n}=\underbrace{x^{-1}*x^{-1}*\ldots *x^{-1}}_{\text{n darab}}=(x^{-1})^n

Azaz x-nek a -n-edik hatványa alatt x inverzének az n-edik hatványát értjük.

Megjegyzés:

E definíció tehát kiterjeszti a 18.8. Tételben bevezetett jelölésmódot a csak pozitív kitevőkről tetszőleges egész kitevőre, beleértve a 0 és a negatív kitevőket is. Egy x elem 0 kitevős hatványának természetesen csak abban az esetben van értelme, ha a műveletre nézve létezik neutrális elem. Ehhez hasonlóan a negatív kitevős hatványoknak pedig csak akkor van értelme, ha x-nek a műveletre nézve létezik inverze. Ezen túlmenően a definíció a 18.8. Tételben szereplő értelmezéssel ellentétben tetszőleges algebrai struktúra tetszőleges asszociatív műveletére – tehát nem kizárólag egy gyűrű „szorzás” műveletére – vonatkoztatható.

A hatványkifejezések segítségével tehát tömören tudjuk kifejezni azt, hogy egy műveletet sokszor kell elvégezni. Gyakori a szakirodalomban, hogy amennyiben a műveletet a + szimbólum jelöli – ez tipikusan kommutatív műveletek esetén szokott így lenni –, akkor x^n helyett az nx írásmódot alkalmazzuk, és hatvány helyett többszörösről beszélünk. Ez azonban nem tévesztendő össze az oszthatóság kapcsán a 16.1. Definíció megismert „többszörös” fogalmával. Ott ugyanis egy R gyűrű esetén az ak kifejezés alatt az a gyűrűelem k gyűrűelemmel vett többszörösét értettük, ami tehát egy darab „szorzás” az R gyűrűben. Ezzel szemben a most megismert na jelölés azt jelenti, hogy az a elemet n-szer kell „összeadni” saját magával az R gyűrűben. Azaz:

na=\underbrace{a+a+a+\ldots +a}_{\text{n darab}}

Most igazoljuk, hogy a pozitív kitevős hatványozás azonosságairól szóló 18.8. Tétel összefüggései érvényben maradnak tetszőleges egész kitevők esetén is.

24.10. Tétel (Egész kitevős hatványozás azonosságai):

Legyen H tetszőleges halmaz, amelyen értelmezve van egy \cdot szimbólummal vagy egymás után írással jelölt asszociatív művelet. Tegyük fel továbbá, hogy e műveletre nézve létezik neutrális elem, és legyenek a és b a H két invertálható eleme. Ekkor tetszőleges – tehát nem feltétlenül csak pozitív – n és k egész számok esetén teljesülnek az alábbi tulajdonságok:

  1. Ha a és b felcserélhetők, azaz ab=ba, akkor (a\cdot b)^n=a^n\cdot b^n
  2. (a^n)^k = a^{n\cdot k}
  3. a^n\cdot a^k=a^{n+k}
  4. a^{-n}=(a^n)^{-1}, azaz az a^{-n} hatvány az a^n hatvány inverze.

Bizonyítás:

Tegyük fel először, hogy n és k mindketten pozitívak.

Ekkor az 1., 2., és 3. tulajdonságok igazolása szinte szóról szóra megegyezik a 18.8. Tétel bizonyításának gondolatmenetével. Mindössze két különbség van. Egyrészt most a tétel szövegéből tudjuk, hogy a \cdot művelet asszociatív, emiatt nem kell hivatkoznunk a 14.12. Definíció szerinti 4. gyűrűaxiómára – amit amúgy nem is tudnánk megtenni, hiszen most nem gyűrűről van szó. Másrészt pedig az 1. tulajdonság esetén ugyancsak a tétel szövegéből tudjuk, hogy ab=ba, így nem kell hivatkoznunk a művelet kommutativitására sem.

A 4. tulajdonsághoz az inverz elem 14.9. Definíciója alapján az alábbi két dolgot kell igazolni (itt e-vel jelöltük a \cdot művelet neutrális elemét):

\begin{aligned}a^{-n}\cdot a^n&=e \\ a^n\cdot a^{-n}&=e\end{aligned}

Egyrészt a 24.9. Definíció alapján a^{-n}=(a^{-1})^n, továbbá a és a^{-1} felcserélhetők, hiszen a 14.9. Definíció szerint a\cdot a^{-1}=a^{-1}\cdot a=e. Másrészt, mivel az 1. tulajdonságot már bizonyítottuk pozitív n esetén, ezért ezt most felhasználhatjuk. Ez alapján egyrészt:

a^{-n}\cdot a^n=(a^{-1})^n\cdot a^n =(a^{-1}\cdot a)^n=e^n=e

Másrészt:

a^n\cdot a^{-n}=a^n\cdot (a^{-1})^n =(a\cdot a^{-1})^n=e^n=e

Így tehát pozitív n esetén a^n és a^{-n} valóban egymás inverzei.

Most tegyük fel, hogy a két kitevő közül legalább az egyik 0. Ekkor a 24.9. Definícióból azonnal adódik mind a 4 tulajdonság. Ha például n=0:

  1. (a\cdot b)^0=e^0=e=e\cdot e=a^0\cdot b^0, méghozzá függetlenül attól, hogy a és b felcserélhető-e vagy nem.
  2. (a^0)^k=e^k=e=a^0=a^{0\cdot k}. Itt az e^k=e lépésnél kihasználtuk, hogy a neutrális elem önmaga inverze, így ez valóban teljesül függetlenül attól, hogy k pozitív, negatív vagy esetleg 0.
  3. a^0\cdot a^k=e\cdot a^k=a^k=a^{0+k}
  4. Egyrészt mivel 0=-0, ezért a^{-0}=a^0=e. Másrészt mivel a neutrális elem önmaga inverze, ezért (a^0)^{-1}=e^{-1}=e. Vagyis valóban a^{-0}=(a^0)^{-1}.

Ha pedig k=0, akkor a 2. és 3. tulajdonságok nyilván teljesülnek, hiszen egyrészt (a^n)^0=e=a^0=a^{n\cdot 0}, másrészt a^n\cdot a^0=a^n\cdot e=a^n=a^{n+0}. Az 1. és 4. tulajdonságokkal ebben az esetben nem kell foglalkoznunk, mivel azokban nem szerepel a k kitevő.

Már csak azok az esetek maradtak, amikor a két kitevő közül legalább az egyik negatív. Legyen például n negatív. Az átláthatóság érdekében vezessük be az m=-n jelölést. Ekkor m pozitív, és ezt a továbbiakban kihasználjuk.

Most igazoljuk az 1. tulajdonságot negatív n-re. A bevezetett jelölésünket alkalmazhatjuk: (ab)^n=(ab)^{-m}. Mivel ugye m pozitív, ezért felhasználhatjuk a 4. tulajdonságot, hiszen azt pozitív kitevőkre már igazoltuk. Ez alapján tehát:

(ab)^{-m}=((ab)^m)^{-1}=\ldots

A külső zárójelen belüli kifejezésre ugyancsak m pozitivitása miatt alkalmazható az 1. tulajdonság, hiszen azt szintén igazoltuk pozitív kitevőkre:

\ldots=(a^mb^m)^{-1}=\ldots

Mivel a tétel szövege alapján most azt feltételezzük, hogy a és b felcserélhetők, ezért ebből következik, hogy a zárójelen belüli a^m és b^m szintén felcserélhetők. Ezek szorzata ugyanis az alábbi 2m tényezős szorzat:

\underbrace{a\cdot a\cdot \ldots \cdot a}_{\text{m darab}} \cdot \underbrace{b\cdot b\cdot \ldots \cdot b}_{\text{m darab}}

Itt egymás mellett álló a és b tényezők cserélgetésével nyilván elérhető, hogy minden b tényező a baloldalra kerüljön. Mivel tehát a^m és b^m felcserélhetők, ezért a 24.2. Tétel alapján az (a^mb^m)^{-1} kifejezés tovább alakítható:

\ldots=(a^m)^{-1}\cdot (b^m)^{-1}=\ldots

Most viszont ismét lehet alkalmazni a 4. tulajdonságot, hiszen m pozitív:

\ldots=a^{-m}\cdot b^{-m}

Összefoglalva azt kaptuk tehát, hogy (ab)^{-m}=a^{-m}b^{-m}. Visszafelé alkalmazva az m=-n jelölést, ez végülis az 1. tulajdonságnak felel meg.

Most a 4. tulajdonságot igazoljuk negatív n esetén. Maradjunk továbbra is az m=-n jelölésnél. Mivel m pozitív, és a 4. tulajdonságot pozitív kitevőkre már igazoltuk, ezért igaz az alábbi:

a^{-m}=(a^m)^{-1}

Visszafelé alkalmazva az m=-n jelölést ez tehát azt jelenti, hogy, hogy a^n és a^{-n} negatív n esetén is egymás inverzei. Tehát a 4. tulajdonság szerinti a^{-n}=(a^n)^{-1} összefüggés valóban teljesül negatív n esetén is.

Most igazoljuk a 2. tulajdonságot negatív n-re és pozitív k-ra. Maradjunk továbbra is az m=-n jelölésnél, azaz (a^n)^k=(a^{-m})^k. Ekkor mivel m pozitív, ezért a 24.9. Definíció alapján:

(a^{-m})^k=((a^{-1})^{m})^k=\ldots

Ha most k pozitív, akkor alkalmazhatjuk a pozitív kitevőkre már bizonyított 2. tulajdonságot. Eszerint tehát:

\ldots=(a^{-1})^{mk}=\ldots

Mivel pedig m is és k is pozitív, ezért mk is az, vagyis ismét a 24.9. Definíció alapján:

\ldots=a^{-mk}

Visszafelé alkalmazva az m=-n jelölést, ez végülis a 2. tulajdonságnak felel meg.

Most igazoljuk a 2. tulajdonságot negatív n-re és szintén negatív k-ra. Maradjunk továbbra is az m=-n jelölésnél, de emellé vezessük be az l=-k jelölést is, azaz (a^n)^k=(a^{-m})^{-l}. Ekkor mivel m pozitív, ezért a 24.9. Definíció alapján:

(a^{-m})^{-l}=((a^{-1})^{m})^{-l}=\ldots

Alkalmazhatjuk a már igazolt 4. tulajdonságot:

\ldots=(((a^{-1})^{m})^l)^{-1}=\ldots

Mivel m is és l is pozitív, ezért alkalmazhatjuk a pozitív kitevőkre már igazolt 2. tulajdonságot:

\ldots=((a^{-1})^{ml})^{-1}=\ldots

Itt ugye ml pozitív, ezért ismét a 24.9. Definíció alapján:

\ldots=(a^{-ml})^{-1}=\ldots

Végül ismét a már igazolt 4. tulajdonság miatt:

\ldots=((a^{ml})^{-1})^{-1}=a^{ml}

Visszafelé alkalmazva az m=-n és az l=-k jelöléseket, ez végülis a 2. tulajdonságnak felel meg.

Végül igazolni kell a 2. tulajdonságot pozitív n-re és negatív k-ra. Ismét vezessük be az l=-k jelölést, azaz (a^n)^k=(a^n)^{-l}. Ekkor a már igazolt 4. tulajdonság miatt:

(a^n)^{-l}=((a^n)^l)^{-1}=\ldots

Mivel n és l pozitívak, és a 2. tulajdonságot már igazoltuk pozitív kitevőkre, ezért az ebben az esetben alkalmazható:

\ldots=(a^{nl})^{-1}=\ldots

Ez viszont újból a 4. tulajdonság miatt az alábbival egyezik meg:

\ldots=a^{-nl}

Visszafelé alkalmazva az l=-k jelölést, ez végülis a 2. tulajdonságnak felel meg.

Már csak a 3. tulajdonságot kell bizonyítani azokban az esetekben, amikor n és k közül legalább az egyik negatív. Mivel itt n és k szerepe teljesen szimmetrikus, ezért csak azt az esetet fogjuk igazolni, amikor n negatív, k pedig bármi más. Fordított esetben – tehát amikor k negatív, n pedig bármi más – ugyanezt a gondolatmenetet kellene végigjátszani k és n szerepének felcserélésével. A k=0 esettől most nyugodtan eltekinthetünk, hiszen azt már igazoltuk.

Vezessük be a jól megszokott m=-n jelölést, azaz a^na^k=a^{-m}a^k. Ekkor ugye m pozitív lesz, tehát a 24.9. Definíció szerint az alábbi szorzatot kaptuk:

a^{-m}\cdot a^k=(a^{-1})^ma^k=\underbrace{a^{-1}a^{-1}\ldots a^{-1}}_{\text{m darab}}\cdot a^k

Ha k negatív, akkor vezessük be ismét az l=-k jelölést is. Ekkor a fenti szorzatban további l darab, tehát összesen m+l darab a^{-1} tényező fog szerepelni. Mivel m+l pozitív, ezért:

a^{-m}a^{-l}=(a^{-1})^{m+l}=a^{-(m+l)}

Visszafelé alkalmazva az m=-n és az l=-k jelöléseket, a kitevőben végülis valóban n+k szerepel, ahogyan a 3. tulajdonság állítja.

Ha k pozitív, akkor a fenti szorzatban m darab a^{-1} tényező és k darab a tényező szerepel, azaz:

a^{-m}\cdot a^k=\underbrace{a^{-1}a^{-1}\ldots a^{-1}}_{\text{m darab}}\cdot \underbrace{aa\ldots a}_{\text{k darab}}

Az egymás mellett álló a és a^{-1} tényezők ugye szép sorban kiütik egymást, mivel egymás inverzei. Kérdés tehát, hogy melyikből van több. Ha m\leq k, akkor legalább annyi a tényező van, mint a^{-1} tényező, így ebben az esetben az a tényezőkből fog megmaradni k-m darab. Azaz ebben az esetben:

a^{-m}\cdot a^k=a^{k-m}

Visszafelé alkalmazva az m=-n jelölést, a kitevőben végülis valóban n+k szerepel, ahogyan a 3. tulajdonság állítja.

Ha viszont m\gt k, akkor több a^{-1} tényező van, mint a, ezért ebben az esetben az a^{-1} tényezőkből fog megmaradni m-k darab. Azaz:

a^{-m}\cdot a^k=(a^{-1})^{m-k}=\ldots

Az m-k kitevő m\gt k miatt biztosan pozitív, ezért a 24.9. Definíció alapján ezt kapjuk:

\ldots=a^{-(m-k)}=a^{k-m}

Visszafelé alkalmazva az m=-n jelölést, a kitevőben ebben az esetben is n+k szerepel, ahogyan a 3. tulajdonság állítja.

Így tehát a közös modulusokon és a Bézout-lemmán alapuló támadás valóban működik azokban az esetekben, amikor az x üzenet által reprezentált [x]_m maradékosztály invertálható, azaz ő egy redukált maradékosztály. Joggal merülhet fel a kérdés, hogy vajon mi a helyzet akkor, ha [x]_m nem redukált maradékosztály, hiszen ekkor nem értelmezhetők az ő negatív kitevős hatványai.

Nos az a helyzet, hogy ekkor amúgyis sokkal nagyobb a baj, hiszen ha x-nek van 1-től különböző közös osztója az m modulussal, akkor nyilván az x^{e_1} és x^{e_2} hatványoknak is van. Ők viszont a támadó birtokába jutott y_1 és y_2 kódszövegekkel kongruensek modulo m, és így a 20.14. Tétel alapján [y_1]_m és [y_2]_m sem lehetnek redukált maradékosztályok. Márpedig ekkor a támadó az euklidészi algoritmus segítségével könnyedén megkaphatja y_1 (vagy y_2) és m kitüntetett közös osztóját, tehát végülis m egyik prímtényezőjét. Ebből könnyedén kiszámíthatja a másik prímtényezőt, és ezek birtokában a titkos kulcsot. Sőt, ugyanezt a küldő fél is megteheti, hiszen ugye maga az eredeti x üzenet sem volt relatív prím m-hez.

Akkor ezek szerint mégsem lenne biztonságos az RSA? Hiszen ez alapján ha sikerül találni egy nem redukált modulo m maradékosztályt, akkor lényegében az euklidészi algoritmus lefuttatásával a titkos kulcshoz szükséges prímtényezők is kiszámíthatók. Nos, ez valóban így van, pusztán annyi a gond, hogy ehhez találni kéne egy nem redukált maradékosztályt. Márpedig ez gyakorlatilag olyan, mintha tűt keresnénk a szénakazalban – ráadásul a szóban forgó számok nagyságrendje miatt hatványozottan. Másként fogalmazva egy euklidészi algoritmusnyi időt leszámítva nem könnyebb ilyen maradékosztályt találni, mintha eleve magukat a prímtényezőket kezdenénk el keresgélni. Tehát nyugodtan feltételezhetjük, hogy a támadóhoz kerülő y_1 és y_2 kódszövegek relatív prímek a modulushoz, ennek teljesülése ugyanis gyakorlatilag biztos.

Most azonban térjünk vissza a csoportelmélethez, és ismerkedjünk meg egy újabb fontos fogalommal, amelyre szükségünk lesz a Miller-Rabin-prímteszttel kapcsolatos bizonyításhoz.

Csoportelem rendje

Az előző szakaszban tehát kiterjesztettük a hatványozást a 0 és a negatív kitevőkre is minden olyan elem esetén, amelynek létezik inverze a szóbanforgó műveletre nézve. Minthogy egy csoportban minden elemnek létezik inverze a csoportműveletre nézve, ezért az előző szakaszban bizonyított összefüggések nyilván érvényesek lesznek bármilyen csoportban.

Számunkra elsősorban a véges csoportok az érdekesek, mint amilyen például a \Z/n\Z maradékosztálygyűrű multiplikatív csoportja is. Vizsgáljuk meg például a (\Z/10\Z)^{\times} multiplikatív csoport elemeinek hatványait. Az alábbi táblázat minden sorában egy-egy csoportelem hatványai szerepelnek az első néhány pozitív kitevőre, amely kitevőknek az egyes oszlopok felelnek meg:

\begin{array}{c|cccccc} &1&2&3&4&5&6 \\ \hline [1]_{10} & [1]_{10} & [1]_{10} & [1]_{10} & [1]_{10} & [1]_{10} & [1]_{10} \\ [3]_{10} & [3]_{10} & [9]_{10} & [7]_{10} & [1]_{10} & [3]_{10} & [9]_{10} \\ [7]_{10} & [7]_{10} & [9]_{10} & [3]_{10} & [1]_{10} & [7]_{10} & [9]_{10} \\ [9]_{10} & [9]_{10} & [1]_{10} & [9]_{10} & [1]_{10} & [9]_{10} & [1]_{10} \end{array}

Például a [3]_{10} maradékosztály harmadik hatványa a [3^3]_{10}=[27]_{10}=[7]_{10} maradékosztály, amely a táblázat második sorának harmadik oszlopában szerepel.

A táblázatot figyelve észrevehetünk egy furcsa jelenséget: egy adott elemnek meghatározott számú különböző hatványa van, amelyek periodikusan ismétlődnek a kitevő növelésével. A maradékosztályoknak egy fontos tulajdonsága, hogy összesen hány különböző hatványuk létezik a maradékosztálygyűrű multiplikatív csoportjában. Ez elvezet az elemrend fogalmához, amelyet az alábbi definícióban tetszőleges csoportra – tehát nem csak a maradékosztálygyűrűk multiplikatív csoportjaira – fogalmazunk meg.

24.11. Definíció (Csoportelem rendje):

Legyen G tetszőleges csoport, g pedig ennek valamely eleme. Ekkor g egymástól különböző hatványainak a számát g rendjének nevezzük, és az angol „order” kifejezésre utalva o(g)-vel jelöljük. Ha g-nek végtelen sok különböző hatványa létezik a G csoportban, akkor azt mondjuk, hogy g rendje végtelen. Jelekkel: o(g)=\infty.

Az alábbiakban a fenti táblázat alapján felsoroltuk a (\Z/10\Z)^{\times} multiplikatív csoport elemeinek rendjeit:

\begin{aligned}o([1]_{10})&=1 \\ o([3]_{10})&=4 \\ o([7]_{10})&=4 \\ o([9]_{10})&=2\end{aligned}

Most igazoljuk az elemrenddel kapcsolatos legfontosabb összefüggéseket:

24.12. Tétel:

Legyen G tetszőleges csoport, g ennek valamely eleme, e pedig az egységelem. Ha g rendje véges, akkor tetszőleges n és k egész számok esetén igazak az alábbiak:

  1. g^k=g^n akkor és csak akkor teljesül, ha fennáll az o(g)|k-n oszthatóság, ami a 20.1. Tétel 3. pontja alapján a k\equiv n\pmod{o(g)} kongruenciát jelenti.
  2. g^k=e akkor és csak akkor teljesül, ha fennáll az o(g)|k oszthatóság, ami a 20.1. Tétel 3. pontja alapján a k\equiv 0\pmod{o(g)} kongruenciát jelenti.
  3. A g elem hatványai o(g) szerint periodikusan ismétlődnek.
  4. A g elem o(g) rendje a legkisebb pozitív kitevő, amelyre g-t emelve az egységelemet kapjuk.
  5. o(g)=1 akkor és csak akkor, ha g=e.

Ha g rendje végtelen, akkor g bármely két hatványa különbözik.

Bizonyítás:

Jelöljük I-vel azt a halmazt, amely olyan i egész számokból áll, amelyekre teljesül az alábbi:

g^i=e

Azaz I azon kitevők halmaza, amelyekre a g elemet emelve a G csoport egységelemét kapjuk.

Az I halmaz zárt az egész számok összeadására nézve, hiszen ha i\in I és j\in I, akkor I definíciója miatt ugye g^i=e és g^j=e. Ám ekkor a 24.10. Tétel 3. pontja alapján g^{i+j}=g^i\cdot g^j=e\cdot e=e, és így szintén I definíciója miatt i+j\in I.

Továbbá az I halmaz zárt tetszőleges egész számmal való szorzásra is, hiszen ha i\in I és s tetszőleges – tehát nem feltétlenül I-beli egész szám –, akkor egyrészt I definíciója miatt g^i=e. Másrészt viszont a 24.10. Tétel 2. pontja alapján g^{i\cdot s}=(g^i)^s=e^s=e, és így szintén I definíciója miatt i\cdot s\in I.

Végül egyrészt I tartalmazza a 0 egész számot, hiszen a 24.9. Definíció szerint g^0=e. Másrészt az I halmaz zárt az egész számok ellentettképzésére is, hiszen ha i\in I, akkor I definíciója miatt g^i=e, ám ekkor a 24.10. Tétel 4. pontja miatt g^{-i}=(g^i)^{-1}=e^{-1}=e, és így szintén I definíciója miatt -i\in I.

Az I halmaz tehát a 18.15. Tétel és a 18.18. Definíció alapján egy ideál az egész számok \Z gyűrűjében.

Ezek után tegyük fel, hogy g^k=g^n. Szorozzuk meg az egyenlet mindkét oldalát g^n inverzével, azaz a 24.10. Tétel 4. pontja alapján g^{-n}-nel. Ekkor az alábbit kapjuk:

g^k\cdot g^{-n}=\underbrace{g^n\cdot g^{-n}}_{=e}

Ez viszont a 24.10. Tétel 3. pontja miatt az alábbival ekvivalens:

g^{k-n}=e

Vagyis g^k=g^n pontosan akkor teljesül, ha k-n\in I. Ez viszont a 18.20. Definíció értelmében épp azt jelenti, hogy teljesül az alábbi, I ideál szerinti kongruencia:

k\equiv n\pod I

Mivel a 17.19. Tétel alapján \Z euklidészi gyűrű, ezért a 19.16. Tétel miatt I szükségképpen csak főideál lehet, azaz egyetlen elemmel generálható. Jelöljük ezt a generátorelemet d-vel. Az I ideál tehát a 20.9. Tétel értelmében d többszöröseiből áll, amelyről az általánosság megsértése nélkül feltehető, hogy nemnegatív. Ha ugyanis d negatív lenne, akkor az ő ellentettje lenne pozitív, és így a 16.8. Tétel 1. pontja értelmében d-nek asszociáltja lenne. Azaz pontosan ugyanazok lennének a többszörösei, mint d-nek, és így őt választhatnánk I generátorelemének.

Feltételezve tehát, hogy d nemnegatív, a fenti ideál szerinti kongruencia a 20.1. Tétel alapján az alábbi kongruenciával ekvivalens:

k\equiv n\pmod d

A g csoportelem bármely két hatványa tehát pontosan akkor egyezik meg, ha a két hatványkitevő ugyanabba a modulo d maradékosztályba esik. Másként fogalmazva g rendje épp a modulo d maradékosztályok száma lesz. Két eset lehetséges: d=0 vagy d\gt 0.

Első esetben a 20.4. Tétel alapján bármely két kitevő különböző maradékosztályba tartozik, tehát g bármely két különböző kitevős hatványa különböző lesz, és így g rendje valóban végtelen.

Második esetben szintén a 20.4. Tétel miatt a modulo d maradékosztályok száma, és így g rendje d, azaz:

o(g)=d

Ezt behelyettesítve a fenti kongruenciába tehát megkaptuk a tétel 1. állítását. A 2. állítás ennek speciális esete, amikoris n=0. A 3. állítás könnyen adódik a 20.4. Tételből. Ez alapján ugyanis ha rögzítünk egy tetszőleges a kitevőt, akkor pontosan az i\cdot o(g) + a alakban felírható kitevők lesznek a-val azonos maradékosztályban – ahol i tetszőleges egész szám –, azaz g hatványai valóban o(g) periódussal ismétlődnek.

A 4. állítás a 17.2. Lemma következménye. Az egységelemet adó kitevők ugyanis épp az I ideál elemei, amelyek – mint láttuk – mindannyian o(g) többszörösei, és így biztosan nem kisebbek o(g)-nél.

Végül az 5. állítás: Ha o(g)=1, akkor a 20.1. Tétel 4. pontja alapján a k\equiv n\pmod{o(g)} kongruencia mindig teljesül, és így bármely kitevő esetén az egységelemet kapjuk – beleértve természetesen az 1-es kitevőt is. Visszafelé: Ha g=e, akkor g-nek már az első hatványa is az egységelem. Mivel az 1 kitevőnél nincs kisebb pozitív egész kitevő, ezért a már bizonyított 4. állítás alapján o(g)=1.

A részcsoportok kapcsán szó volt róla, hogy hogyan lehet könnyen ellenőrizni azt, hogy egy csoport valamely H részhalmaza részcsoportot alkot-e vagy sem. Ennek feltételeit a 24.5. Tételben határoztuk meg. Eszerint elegendő azt ellenőrizni, hogy H zárt-e a csoportműveletre, és az elletettképzésre nézve, valamint tartalmazza-e a csoport egységelemét. Az imént bizonyított elemrendre vonatkozó összefüggések alapján most igazoljuk, hogy véges csoportok esetén a műveleti zártságból már következik a másik két feltétel.

24.13. Következmény:

Legyen G tetszőleges véges csoport, H pedig ennek egy tetszőleges nemüres részhalmaza. A H halmaz akkor és csak akkor részcsoport G-ben, ha zárt a G csoport műveletére nézve.

Bizonyítás:

Ha H részcsoport, akkor teljesíti a 24.5. Tétel feltételeit, így a műveleti zártságot is.

Visszafelé: Tegyük fel, hogy H olyan részhalmaz, amely zárt a csoportműveletre nézve, legyen g tetszőleges H-beli elem, továbbá jelöljük G egységelemét e-vel. Mivel G véges, ezért g-nek nem lehet végtelen sok különböző hatványa, és így az o(g) rend is véges. Azt tudjuk, hogy H zárt a csoportműveletre nézve, azaz tartalmazza g minden hatványát, így a g^{o(g)} hatványt is. A 24.12. Tétel 4. pontja alapján azonban g^{o(g)}=e, így tehát H valóban tartalmazza az egységelemet.

Végül szintén a műveleti zártság miatt H tartalmazza a g^{o(g)-1} hatványt is. Ez viszont épp g inverze, hiszen a 24.10. Tétel 3. pontja alapján őket összeszorozva épp az egységelemet kapjuk:

g\cdot g^{o(g)-1}=g^{1+o(g)-1}=g^{o(g)}=e

A H halmaz tehát zárt az inverzképzésre is. Teljesülnek tehát a 24.5. Tétel feltételei, következésképp H valóban részcsoport.

Megjegyzés:

A tétel bizonyításában G végességére pusztán azért volt szükség, mert ebből következett, hogy minden elem rendje szintén véges – ami ugye a bizonyítás kulcsa volt. Azonban visszafelé ez nem feltétlenül van így. Azaz abból, hogy minden elem rendje véges még nem következik, hogy maga a csoport is véges. Torziócsoportoknak nevezzük az olyan csoportokat, amelyeknél csak az elemrendek végességét követeljük meg, de magának a csoport rendjének a végességét nem feltétlenül. Nyilván minden véges csoport torziócsoport, ám léteznek végtelen torziócsoportok is. Ilyenre azonban az eddigi ismereteink alapján sajnos nem tudunk példát mutatni. Mindenesetre a tétel szövegében elegendő lett volna annyit kikötni, hogy G legyen torziócsoport.

Végül ismertetünk egy további egyszerű következményt, amely az egyes elemek rendjei és a csoport rendje között mond ki egy, a továbbiakban hasznos összefüggést.

24.14. Következmény:

Ha G véges csoport, akkor G bármely elemének rendje osztója G rendjének.

Bizonyítás:

Legyen g a G csoport tetszőleges eleme, és jelöljük H-val azt a halmazt, amely pontosan g hatványaiból áll. Ekkor H nyilván nemüres, hiszen tartalmazza legalább g-t. Továbbá zárt a G csoport műveletére nézve, ugyanis g bármely két hatványát összeszorozva ugyancsak g-nek egy hatványát kapjuk, hiszen a 24.10. Tétel 3. pontja miatt:

g^k\cdot g^n=g^{k+n}

Mivel G véges, ezért a 24.13. Következmény értelmében H részcsoport G-ben. A Lagrange-tétel (24.8. Tétel) miatt tehát teljesül az alábbi oszthatóság:

|H|\ |\ |G|

Mivel azonban H a g elem összes létező hatványaiból áll, ezért |H|=o(g). Ezt behelyettesítve a fenti oszthatóságba megkapjuk a tétel állítását.

Egész számok p-adikus rendje

E rövid csoportelméleti bevezető után a csoport rendje és a csoportelem rendje mellé a kóbor apácák megtévesztésére most bevezetünk egy harmadik rendfogalmat, amelyet egy hasznos moduláris aritmetikai összefüggés bizonyításához fogunk felhasználni. Az előző részben a Miller-Rabin-prímteszt alapgondolatának ismertetése kapcsán lényegében már találkoztunk vele. Ott arról volt szó, hogy adva volt egy n pozitív páratlan szám, és azt kellett meghatározni, hogy ebben az esetben az n-1 páros szám hányszor osztható 2-vel. Azaz kerestük azt az e\geq 1 kitevőt, amely esetén az n-1 páros szám még osztható 2^e-vel, viszont 2^{e+1}-gyel már nem. Most ezt általánosítjuk 2 helyett tetszőleges pozitív p prímszámra.

24.15. Definíció (Egész szám p-adikus rendje):

Legyen a\neq 0 egy tetszőleges nemnulla egész szám, p\gt 0 pedig valamilyen pozitív prímszám. Azt mondjuk, hogy az a egész szám p-adikus rendje k (ennek jele: v_p(a)=k), amennyiben igazak az alábbiak:

\begin{aligned}p^k&|a \\ p^{k+1}&\nmid a\end{aligned}

A 0 egész szám p-adikus rendjét végtelennek definiáljuk, azaz v_p(0)=\infty.

Visszatérve a Miller-Rabin-prímteszt példájára, amennyiben tehát az n-1 páratlan szám felírható 2^ek alakban, ahol k már páratlan, akkor a mostani jelölésünkkel ezt így írhatjuk:

v_2(n-1)=e

A 2 prímszám esetén ezt a mennyiséget speciálisan diadikus rendnek nevezzük.

Most egy hasznos segédtételt ismertetünk, amely azzal a kérdéssel foglalkozik, hogyha két egész számnak vesszük valamilyen hatványát, és képezzük ezek különbségét, akkor mi lesz ennek a különbségnek a p-adikus rendje, amennyiben a két egész szám első hatványainak különbségére már ismerjük ezt a mennyiséget. Ez az összefüggés “Lifting the exponent lemma” néven ismeretes. Mi ennek most egy speciális esetét ismertetjük, amikoris a hatványkitevő megegyezik a p prímszámmal.

24.16. Lemma:

Legyenek adottak x és y tetszőleges egész számok, valamint egy p pozitív prímszám, amelyekre teljesülnek az alábbiak:

\begin{aligned}x&\neq y\\v_p(xy)&=0\\v_p(x-y)&\neq 0\end{aligned}

Ekkor érvényes az alábbi összefüggés:

v_p(x^p-y^p)=v_p(x-y)+1

Bizonyítás:

Mivel x\neq y, ezért x-y\neq 0, és így v_p(x-y) a 24.15. Definíció alapján egy véges nemnegatív szám, amiről a tétel szövege alapján tudjuk, hogy nemnulla, tehát v_p(x-y)\geq 1. Jelöljük ezt a számot k-val, azaz vezessük be az alábbi jelölést:

k=v_p(x-y)

Ez a p-adikus rend 24.15. Definíciója szerint azt jelenti, hogy az x-y különbség prímtényezős felbontásában a p prímtényező a k-adik hatványon szerepel. Létezik tehát olyan m egész szám, amely tovább már nem osztható p-vel, és teljesül rá az alábbi:

x-y=p^km

Az x tehát kifejezhető a következőképpen:

x=p^km+y

Most vizsgáljuk meg, hogyan néz ki x=p^km+y-nak a p-edik hatványa:

x^p=(p^km+y)^p=?

Ez ugye egy p darab tényezőből álló kifejezés, amelyben minden tényező egy-egy kéttagú összeg, nevezetesen ez: (p^km+y). Az áttekinthetőség kedvéért a zárójelekben szereplő első tagra átmenetileg vezessük be a z=p^km jelölést. Ekkor tulajdonképpen az alábbi szorzást kéne tehát elvégezni:

\underbrace{(z+y)\cdot (z+y)\cdot \ldots \cdot (z+y)}_{\text{p darab}}

Vizsgáljuk meg, hogy milyen alakot ölt az eredmény, ha felbontjuk ezt a p darab zárójelet. A 14.12. Definícióban szereplő disztributivitási szabályok alapján ezt úgy kell elvégezni, hogy minden zárójelből az összes lehetséges kombinációban kiválasztunk pontosan egy tagot, ezeket összeszorozzuk egymással, és az így kapott szorzatokat összeadjuk.

Megtehetjük például, hogy mind a p darab zárójelből a z tagot választjuk, és 0 darab zárójelből választjuk az y tagot. Ez a választás a z^py^0=z^p szorzatot fogja eredményezni, és nyilván csak egyféleképpen tudjuk megtenni. A végeredmény tehát így fog kezdődni:

(z+y)^p = z^p + \ldots

Egy másik választás lehet, amikor 1 darab zárójelből választjuk ki az y tagot, és a maradék p-1 darab zárójelből továbbra is a z tagot választjuk. Ezek a választások mind a z^{p-1}y^1 szorzatot fogják eredményezni. Ilyen szorzatból viszont már p darab van, hiszen azt az egyetlen y tagot választhatjuk az 1., a 2., a 3., ..., és végül a p-edik zárójelből. A végeredmény tehát így folytatódik:

\begin{aligned}(z+y)^p &= z^p \\ &+ p\cdot z^{p-1}y \\ &+ \ldots\end{aligned}

A következő kombinációk azok lesznek, amelyek esetén 2 darab zárójel esetén választjuk ki az y tagot. Ekkor a fennmaradó p-2 zárójelből a z tagot kell választanunk, tehát ezek a kombinációk mind a z^{p-2}y^2 szorzatot fogják eredményezni. Ezért a z^{p-2}y^2 szorzatból épp annyi fog szerepelni a végeredményben, ahányféleképpen p darab zárójelből ki tudjuk választani azt a 2 darabot, amelyek az y tényezőt adják az adott szorzathoz. Anélkül, hogy bonyolultabb kombinatorikai fejtegetésbe bonyolódnánk, jelöljük ezt a számot A_2-vel. A végeredmény tehát így folytatódik:

\begin{aligned}(z+y)^p &= z^p \\ &+ p\cdot z^{p-1}y \\ &+ A_2\cdot z^{p-2}y^2 \\ &+ \ldots\end{aligned}

Általánosságban ha 0-tól kezdve sorszámozzuk a végeredmény tagjait, akkor az i-edik tag azokat a kombinációkat fogja tartalmazni, amelyek esetén i darab zárójel esetén választjuk ki az y tagot. Ekkor a fennmaradó p-i zárójelből kell a z tagot választanunk, tehát ezek a kombinációk mind a z^{p-i}y^i szorzatot fogják eredményezni. Ilyenből épp annyi fog szerepelni a végeredményben, ahányféleképpen p darab zárójelből ki tudjuk választani azt az i darabot, amelyek az y tényezőt adják az adott szorzathoz. Mivel ismét nem szeretnénk kombinatorikával szórakozni, ezért jelöljük ezt a számot nagyvonalúan A_i-vel. Ezért a végeredmény i-edik tagja így néz ki:

A_i\cdot z^{p-i}y^i

Mindent összevetve tehát (z+y)^p teljes kifejtése így néz ki:

\begin{aligned}(z+y)^p &= A_0\cdot z^p \\ &+ A_1\cdot z^{p-1}y \\ &+ A_2\cdot z^{p-2}y^2 \\ &\ \vdots \\ &+ A_i\cdot z^{p-i}y^i \\ &\ \vdots \\ &+A_{p-1}\cdot zy^{p-1} \\ &+ A_p\cdot y^p\end{aligned}

Ahogyan megállapítottuk már, itt A_0=1 és A_1=p. Továbbá, mivel egyrészt p-féleképp lehet p darab zárójelből kiválasztani azt az egyet, amelyből NEM az y, hanem a z tagot választottuk ki, ezért természetesen A_{p-1}=p. Másrészt pedig egyféleképpen lehet az összes zárójelből az y tagot választani, ezért A_p=1. A többi A_i együttható pontos értékét az úgynevezett binomiális tétel alapján lehet kiszámítani, ám a bizonyítás szempontjából ez most nem érdekes számunkra.

Ha most visszafelé alkalmazzuk a z=p^km jelölést, akkor az x^p=(\underbrace{p^km}_{=z}+y)^p hatványra lényegében ezt a kifejezést kaptuk:

\begin{aligned}x^p&=(\underbrace{p^km}_{=z})^p + p\cdot (\underbrace{p^km}_{=z})^{p-1}y + A_2\cdot (\underbrace{p^km}_{=z})^{p-2}y^2 + \ldots \\ &\ldots + A_{p-2}\cdot (\underbrace{p^km}_{=z})^2y^{p-2} + p\cdot (\underbrace{p^km}_{=z})y^{p-1} + y^p\end{aligned}

Alkalmazva a hatványozás azonosságairól szóló 18.8. Tétel mindhárom pontját:

\begin{aligned}x^p&=p^{pk}m^p + p^{(p-1)k+1}m^{p-1}y + A_2\cdot p^{(p-2)k}m^{p-2}y^2 + \ldots \\ &\ldots + A_{p-2}\cdot p^{2k}m^2y^{p-2} + p^{k+1}my^{p-1} + y^p\end{aligned}

Minket ugye az x_p-y_p különbség p-adikus rendje érdekel. Ezt a különbséget megkapjuk, ha a fenti összegzésből elhagyjuk az utolsó, y^p tagot:

\begin{aligned}x^p-y^p&=p^{pk}m^p + p^{(p-1)k+1}m^{p-1}y + A_2\cdot p^{(p-2)k}m^{p-2}y^2 + \ldots \\ &\ldots + A_{p-2}\cdot p^{2k}m^2y^{p-2} + p^{k+1}my^{p-1}\end{aligned}

Azt kell meghatározni tehát, hogy a fenti kifejezés p-nek legfeljebb hányadik hatványával osztható. Mivel a bizonyítás elején megállapítottuk, hogy k\geq 1, ezért p^{k+1}-gyel minden fenti tag osztható, teljesül tehát az alábbi oszthatóság:

p^{k+1}|x^p-y^p

Most nézzünk ennél 1-gyel magasabb hatványt, azaz p^{k+2}-t. Az utolsó előtti tagig bezárólag szintén minden fenti tag osztható p^{k+2}-vel. Kérdés, hogy mi a helyzet az utolsó, p^{k+1}my^{p-1} taggal.

Az m egész szám biztosan nem tartalmazza a p prímtényezőt, hiszen a bizonyítás elején őt épp így állítottuk elő. Továbbá a tétel szövege szerint v_p(xy)=0, ami a 24.15. Definíció alapján épp azt jelenti, hogy az xy szorzat sem tartalmazza a p prímtényezőt, így tehát maga y sem. A p^{k+1}my^{p-1} szorzat prímtényezős felbontásában p így csak a k+1-edik hatványon szerepel, azaz nem osztható p^{k+2}-vel. Így viszont a teljes összeg sem osztható p^{k+2}-vel, azaz:

p^{k+2}\nmid x^p-y^p

Ezt összevetve a fentebb megállapított p^{k+1}|x^p-y^p oszthatósággal, a 24.15. Definíció szerint lényegében megkaptuk a tétel állítását:

v_p(x^p-y^p)=\underbrace{k}_{=v_p(x-y)}+1

Most az imént bizonyított lemma segítségével egy olyan moduláris aritmetikai összefüggést fogunk igazolni, amely kulcsfontosságú lesz a közvetkező szakaszban.

24.17. Következmény:

Legyen p egy pozitív prímszám, a pedig egy tetszőleges egész szám, amely p-vel osztva 1-et ad maradékul, azaz amelyre teljesül az alábbi kongruencia:

a\equiv 1\pmod p

Ekkor tetszőleges c\geq 1 egész kitevő esetén teljesül az alábbi kongruencia is:

a^{p^{c-1}}\equiv 1\pmod{p^c}

Bizonyítás:

Egyrészt az általánosság megsértése nélkül feltehetjük, hogy a\neq 1, ebben az esetben ugyanis a tétel nyilvánvalóan igaz. Továbbá azt is feltehetjük, hogy a\neq -1, mivel ebben az esetben a -1\equiv 1\pmod p feltétel alapján p csak 2 lehet, és ekkor a tétel ismét nyilvánvalóan igaz.

Másrészt az a egész szám biztosan nem osztható p-vel, hiszen a tétel szövegében szereplő a\equiv 1\pmod p kongruencia alapján 1-et ad maradékul p-vel osztva. Az 1 szintén nem osztható p-vel. Emiatt a 24.15. Definíció szerint a szorzatuk p-adikus rendje biztosan 0.

Harmadrészt az a\equiv 1\pmod p a 20.1. Tétel 3. pontja alapján azt is jelenti, hogy teljesül az alábbi oszthatóság:

p|a-1

Így ismételten a 24.15. Definíció szerint az a-1 különbség p-adikus rendje biztosan nem 0.

Összefoglalva tehát az a és az 1 egész számokra teljesül a 24.16. Lemma mindhárom feltétele, azaz:

\begin{aligned}a&\neq 1\\v_p(a\cdot 1)&=0\\v_p(a-1)&\neq 0\end{aligned}

Ekkor viszont ugye teljesül az alábbi összefüggés:

v_p(a^p-1^p)=v_p(a-1)+1

Ez tehát azt jelenti, hogy az a^p-1 különbség prímtényezős felbontásában 1-gyel többször szerepel p, mint az a-1 felbontásában. Következésképp, mivel ugye teljesül a p|a-1 oszthatóság, ezért szükségképpen teljesülnie kell a p^2|a^p-1 oszthatóságnak is, ami a 20.1. Tétel 3. pontja alapján az alábbi kongruenciát jelenti:

a^p\equiv 1\pmod{p^2}

Most ugyanezt a gondolatmenetet eljátszhatjuk az a^p és az 1 egész számokra is. Egyrészt mivel a\neq 1 és a\neq -1, ezért nyilván a^p\neq 1 is teljesül. Másrészt mivel a-ról tudjuk, hogy nem osztható p-vel, ezért nyilván a^p sem osztható p-vel, azaz v_p(a^p\cdot 1)=0. Harmadrészt mivel teljesül a p^2|a^p-1 oszthatóság, ezért nyilván v_p(a^p-1)\neq 0. Ám ekkor ismét a 24.16. Lemma alapján:

v_p((a^p)^p-1^p)=v_p(a^p-1)+1

Vagyis az (a^p)^p-1=a^{p^2}-1 különbség prímtényezős felbontásában 1-gyel többször szerepel p, mint az a^p-1 felbontásában. Következésképp, mivel ugye teljesül a p^2|a^p-1 oszthatóság, ezért szükségképpen teljesülnie kell a p^3|a^{p^2}-1 oszthatóságnak is, ami a 20.1. Tétel 3. pontja alapján az alábbi kongruenciát jelenti:

a^{p^2}\equiv 1\pmod{p^3}

A fenti gondolatmenetet akárhányszor megismételhetjük, melynek során a c-1-edik lépésben épp a tétel állítását kapjuk:

\begin{aligned}a^{p^3}&\equiv 1\pmod{p^4} \\ a^{p^4}&\equiv 1\pmod{p^5} \\ a^{p^5}&\equiv 1\pmod{p^6} \\ &\vdots \\ a^{p^{c-1}}&\equiv 1\pmod{p^c}\end{aligned}

A nem Miller-Rabin-tanúk csoportja

Most használjuk fel az eddig tanultakat ahhoz, hogy igazolni tudjunk egy alsó becslést a Miller-Rabin-tanúk számára. Ezzel egyúttal az is világossá válik, hogy erre a prímtesztre nézve nem léteznek a Carmichael-számokhoz (23.7. Definíció) hasonló univerzális álprímek.

A 24.3. Definíció utáni megjegyzésben megmutattuk, hogy bármilyen gyűrűben a szorzásra nézve invertálható elemek halmaza csoportot alkot. Így például egy adott n\gt 1 páratlan egész szám esetén a modulo n redukált maradékosztályok is csoportot alkotnak, amelyet (\Z/n\Z)^{\times}-vel jelöltünk. Érdekes kérdés, hogyha n összetett, akkor vajon a redukált maradékosztályok csoportjában a nem Miller-Rabin-tanúk részcsoportot alkotnak-e.

Nos általában nem ez a helyzet. Nézzük például az n=65 esetét. Az Olvasó maga is leellenőrizheti a 23.9. Definíció alapján, hogy például a [8]_{65} és a [18]_{65} redukált maradékosztályok nem Miller-Rabin-tanúk. Kiszámítva a definícióban szereplő e kitevőt és k páratlan számot e=6 és k=1 adódik, hiszen 65-1=2^6\cdot 1. Ezekkel ellenőrizve a Miller-Rabin-kongruenciákat, azok közül mind a [8]_{65}, mind pedig a [18]_{65} maradékosztály esetén valóban teljesül a harmadik:

\begin{array}{cc}\begin{aligned}8\ \cancel{\equiv}\ 1 &\pmod{65} \\ 8\ \cancel{\equiv}\ -1 &\pmod{65} \\ 8^2\equiv -1&\pmod{65} \\ &\vdots\end{aligned} & \begin{aligned}18\ \cancel{\equiv}\ 1 &\pmod{65} \\ 18\ \cancel{\equiv}\ -1 &\pmod{65} \\ 18^2\equiv -1&\pmod{65} \\ &\vdots \end{aligned}\end{array}

Ugyanakkor kettejük szorzata, azaz a [8]_{65}\cdot [18]_{65}=[14]_{65} maradékosztály már Miller-Rabin-tanú, hiszen a [14]_{65}-re a Miller-Rabin-kongruenciák közül egyik sem teljesül:

\begin{aligned}14\ &\cancel{\equiv}\ 1 \pmod{65} \\ 14\ &\cancel{\equiv}\ -1 \pmod{65} \\ 14^2\ &\cancel{\equiv}\ -1\pmod{65} \\ 14^{2^2}\ &\cancel{\equiv}\ -1\pmod{65} \\ 14^{2^3}\ &\cancel{\equiv}\ -1\pmod{65} \\ 14^{2^4}\ &\cancel{\equiv}\ -1\pmod{65} \\ 14^{2^5}\ &\cancel{\equiv}\ -1\pmod{65}\end{aligned}

Azaz a nem Miller-Rabin-tanúk halmazára nem teljesül a műveleti zártság, és így részcsoport sem lehet. Van azonban egy speciális eset, amikor a nem Miller-Rabin-tanúk mégiscsak részcsoportot alkotnak. Nevezetesen amikor n valamilyen prímhatvány. Az alábbi tételben ennél még többet is igazolunk.

24.18. Tétel:

Legyen n egy tetszőleges, 1-nél nagyobb páratlan szám, amely valamilyen prímhatvány. Azaz n=p^c, ahol p valamilyen pozitív, páratlan prímszám, c pedig tetszőleges pozitív kitevő. Jelöljük G_n-nel azon modulo n maradékosztályok halmazát, amelyek NEM Miller-Rabin-tanúi n-nek. Ekkor igazak az alábbiak:

  1. Egy valamilyen a egész szám által reprezentált [a]_n maradékosztály esetén [a]_n\in G_n akkor és csak akkor teljesül, ha fennáll az a^{p-1}\equiv 1\pmod n kongruencia.
  2. A G_n halmaz a \Z/n\Z maradékosztálygyűrű multiplikatív csoportjának egy részcsoportja, azaz G_n\leq (\Z/n\Z)^{\times}.
  3. A G_n halmaz akkor és csak akkor valódi részcsoport – azaz G_n\lt(\Z/n\Z)^{\times} –, ha c\gt 1. Egyébként c=1 esetben G_n=(\Z/n\Z)^{\times}.

Bizonyítás:

Mivel a tételben szereplő G_n halmaz elemei a NEM Miller-Rabin-tanúk, ezért a 23.9. Definíció utáni megjegyzés alapján az biztos, hogy itt csak redukált maradékosztályok lehetnek, azaz G_n\sube (\Z/n\Z)^{\times}.

Ha c=1, akkor n=p^c=p egy prímszám, amelynek a 23.10. Tétel értelmében egyáltalán nincsenek Miller-Rabin-tanúi, azaz ebben az esetben G_n=(\Z/n\Z)^{\times}. Ezzel c=1-re igazoltuk a 2. és 3. állításokat. Mivel n=p most egy prímszám, ezért az 1. állítás a kis Fermat-tételből (22.1. Tétel) azonnal következik, mely szerint bármilyen n=p-hez relatív prím a egész számra teljesül az a^{p-1}\equiv 1\pmod p kongruencia. A 20.14. Tétel alapján az n=p-hez relatív prím egész számok pontosan a redukált maradékosztályokat, azaz a (\Z/n\Z)^{\times} multiplikatív csoport elemeit reprezentálják, ami ugye – mint láttuk – megegyezik a NEM Miller-Rabin-tanúk G_n halmazával.

Az általánosság megsértése nélkül feltehetjük tehát, hogy c\geq 2.

Nézzük az 1. állítást ebben az esetben! Azt kell tehát bizonyítani, hogy az n=p^c egész szám NEM Miller-Rabin-tanúinak a reprezentánselemei, és csak azok elégítik ki az alábbi kongruenciát:

a^{p-1}\equiv 1\pmod{\underbrace{n}_{=p^c}}

Ha az [a]_n maradékosztály nem Miller-Rabin-tanú, akkor egyrészt a 23.9. Definíció utáni megjegyzés alapján csak redukált maradékosztály lehet, és így a 20.14. Tétel szerint a és n=p^c relatív prímek. Ekkor viszont érvényes az Euler-Fermat tétel (20.19. Tétel), miszerint:

a^{\varphi(n)}\equiv 1\pmod n

Másrészt viszont ha [a]_n nem Miller-Rabin-tanú, akkor szintén a 23.9. Definíció utáni megjegyzés szerint nem lehet Fermat-tanú sem. Ez a 23.3. Definíció alapján azt jelenti, hogy fennáll az alábbi kongruencia is:

a^{n-1}\equiv 1\pmod n

A 24.12. Tétel 2. pontja alapján tehát a (\Z/n\Z)^{\times} csoportban az [a]_n elem rendje közös osztója \varphi(n)-nek és n-1-nek. Ez viszont a 17.4. Definíció miatt azt jelenti, hogy osztója a (\varphi(n), n-1) kitüntetett közös osztónak is, azaz teljesül az alábbi oszthatóság:

o([a]_n)|(\varphi(n), n-1)

Alkalmazva az n=p^c helyettesítést a jobboldalon szereplő kitüntetett közös osztóra a 21.5. Tétel alapján, továbbá a 14.12. Definícióban szereplő 5. gyűrűaxióma szerint a következőt kapjuk:

(\underbrace{p^c-p^{c-1}}_{=\varphi(p^c)}, p^c-1)=((p-1)p^{c-1},p^c-1)=\ldots

Szintén a gyűrűaxiómák következménye, hogy a jobboldalon szereplő p^c-1 kifejezésből is kiemelhető a p-1 tényező, méghozzá az alábbi összefüggés miatt, amelyet az Olvasó maga is leellenőrizhet a zárójelek felbontásával:

p^c-1=(p-1)(p^{c-1}+p^{c-2}+\ldots+p+1)

Alkalmazhatjuk tehát a kitüntetett közös osztó kiemelési tulajdonságát (17.9. Tétel), azaz a fenti kitüntetett közös osztóból kiemelhetjük p-1-et:

\ldots=(p-1)\cdot (p^{c-1},p^{c-1}+p^{c-2}+\ldots+p+1)=\ldots

Vegyük észre, hogy az itt szereplő jobboldali p^{c-1}+p^{c-2}+\ldots+p+1 összeg minden tagja osztható p-vel, kivéve az utolsó. Ez az összeg tehát p-vel osztva 1 maradékot ad, azaz a prímtényezői biztosan mind különböznek p-től. Ezzel szemben a baloldali p^{c-1} prímtényezői között csak p szerepel. A két mennyiség emiatt egymáshoz relatív prím, azaz:

\ldots=(p-1)\cdot \underbrace{1}_{=(p^{c-1},p^{c-1}+p^{c-2}+\ldots+p+1)}

Azt kaptuk tehát, hogy ha az [a]_n maradékosztály nem Miller-Rabin-tanú, akkor az ő rendje a (\Z/n\Z)^{\times} csoportban osztója lesz a (\varphi(n),n-1)=p-1 kitüntetett közös osztónak. Ez viszont a 24.12. Tétel 2. pontja alapján épp azt jelenti, hogy valóban teljesül az alábbi kongruencia, ahogyan a tétel állítja:

a^{p-1}\equiv 1\pmod{\underbrace{n}_{=p^c}}

Most nézzük visszafelé! Tegyük fel, hogy teljesül az iménti kongruencia egy a egész számra. Most azt kell bizonyítani, hogy ekkor az [a]_n maradékosztály nem Miller-Rabin-tanú. Mivel n=p^c páratlan, ezért n-1=p^c-1 páros, és így valahányszor osztható 2-vel. Azaz létezik olyan e\geq 1 kitevő és k\geq 1 páratlan egész, hogy:

n-1=p^c-1=2^e\cdot k

Ehhez hasonlóan p-1-hez is létezik olyan f\geq 1 kitevő és l\geq 1 páratlan egész, hogy:

p-1=2^f\cdot l

A korábban már említett p^c-1=(p-1)(p^{c-1}+p^{c-2}+\ldots+p+1) azonosság alapján tudjuk, hogy teljesül az alábbi oszthatóság:

\underbrace{2^fl}_{=p-1}|\overbrace{2^ek}^{=p^c-1}

Mivel l és k páratlan, így ezek prímtényezői között biztosan nem szerepel a 2-es. Ezért a fenti oszthatóság csak úgy teljesülhet, ha fennáll az alábbi két feltétel:

\begin{aligned}f&\leq e \\ l&|k\end{aligned}

Ugye abból indultunk ki, hogy teljesül az a^{p-1}\equiv 1\pmod n kongruencia. Ez az imént bevezetett p-1=2^fl jelölést alkalmazva így írható:

a^{2^fl}\equiv 1\pmod n

Ez a hatványozás azonosságairól szóló 18.8. Tétel 2. pontja miatt így is írható:

(a^l)^{2^f}\equiv 1\pmod n

A 24.12. Tétel 2. pontja alapján tehát az [a^l]_n maradékosztály rendje osztója 2^f-nek. Ez csak úgy lehet, ha ez a rend is valamilyen 2-hatvány egy f-nél nemnagyobb, nemnegatív j kitevővel, azaz o([a^l]_n)=2^j.

Ha j=0, akkor ugye (a^l)^{2^0}=a^l és így teljesül az alábbi kongruencia:

a^l\equiv 1\pmod n

De mivel tudjuk, hogy l|k – azaz k az l-nek többszöröse –, ezért ekkor teljesül az a^k\equiv 1\pmod n kongruencia is. Ez épp a 23.9. Definícióban szereplő első kongruencia, amely szerint tehát [a]_n valóban nem lehet Miller-Rabin-tanú.

Ha j\geq 1, akkor ez az elemrend 24.11. Definíciója miatt azt jelenti, hogy 2^j a legkisebb olyan kitevő, amely esetén az alábbi kongruencia teljesül:

(a^l)^{2^j}\equiv 1\pmod n

Az ennél kisebb kitevőkre ez már nem teljesül, tehát például:

(a^l)^{2^{j-1}}\ \cancel{\equiv}\ 1\pmod n

A felső kongruencia baloldala épp az alsó kongruencia baloldalának négyzete, hiszen:

((a^l)^{2^{j-1}})^2=(a^l)^{2^{j-1}\cdot 2}=(a^l)^{2^j}

Ha most az áttekinthetőség kedvéért bevezetjük az x=(a^l)^{2^{j-1}} jelölést, akkor fenti két kongruencia tulajdonképpen az alábbi két állításnak felel meg:

\begin{aligned}x\ &\cancel{\equiv}\ 1\pmod n \\ x^2&\equiv 1\pmod n\end{aligned}

Az alsó kongruencia a 20.1. Tétel 3. pontja alapján az alábbi oszthatóságot jelenti:

n|x^2-1

Ennek az oszthatóságnak a jobboldala a 14.12. Definícióban ismertetett gyűrűaxiómák miatt szorzatba fejthető:

\underbrace{n}_{=p^c}|(x+1)\cdot (x-1)

Ez az oszthatóság tehát biztosan teljesül. Ugyanakkor az is bizonyos, hogy x+1 és x-1 közül legfeljebb az egyikük prímtényezői között szerepelhet p, hiszen közöttük mindössze 2 a különbség. Más szavakkal az egyikük biztosan relatív prím lesz n=p^c-hez, és így az euklidészi lemma (17.11. Tétel) alapján a másik viszont biztosan osztható lesz n-nel. Azaz az alábbi oszthatóságok közül pontosan az egyik teljesül:

\begin{aligned}n&|x+1 \\ n&|x-1\end{aligned}

Azonban a második oszthatóság lehetetlen, hiszen az a 20.1. Tétel 3. pontja szerint azt jelentené, hogy mégiscsak teljesülne az x\equiv 1\pmod n kongruencia, amiről már láttuk, hogy nem teljesülhet. Következésképp csak az első oszthatóság teljesülhet. Ez viszont ismét a 20.1. Tétel 3. pontja miatt épp az alábbi kongruenciát jelenti:

x\equiv -1\pmod n

Azonban emlékezzünk rá, hogy x-szel tulajdonképpen az (a^l)^{2^{j-1}}=a^{2^{j-1}l} kifejezést jelöltük, ezért ez a kongruencia ennek felel meg:

a^{2^{j-1}l} \equiv -1\pmod n

Mivel korábban már láttuk, hogy k többszöröse l-nek, azaz létezik olyan t egész szám, amely esetén lt=k. Ráadásul mivel a k és l számokról tudjuk, hogy páratlan számok, ezért a t is szükségképpen páratlan. Ha tehát a fenti kongruencia mindkét oldalát t-edik hatványra emeljük (amelyet ugye a 20.2. Tétel 8. pontja alapján tehetünk meg), akkor ezt kapjuk:

a^{2^{j-1}\overbrace{lt}^{=k}} \equiv \overbrace{(-1)^t}^{=-1}\pmod n

Itt a jobboldal valóban -1 marad, hiszen negatív szám páratlanadik hatványa ugyancsak negatív. Végeredményben tehát ezt kaptuk:

a^{2^{j-1}k} \equiv -1\pmod n

Tekintve, hogy j-1 biztosan kisebb a bevezetett e kitevőnél, ezért az alábbi kongruenciák közül biztosan teljesül az egyik:

\begin{aligned}a^k&\equiv -1 \\ a^{2k}&\equiv -1\pmod n \\ a^{4k}&\equiv -1\pmod n \\ &\vdots \\ a^{2^{e-1}\cdot k}&\equiv -1\pmod n\end{aligned}

Ez viszont a 23.9. Definíció alapján azt jelenti, hogy az [a]_n maradékosztály ebben az esetben sem lehet Miller-Rabin-tanú. Ezzel a tétel 1. állítását igazoltuk, miszerint valóban pontosan azok a maradékosztályok nem Miller-Rabin-tanúk – azaz tartoznak bele a tétel szövegében szereplő G_n halmazba –, amelyekre teljesül az alábbi kongruencia:

a^{p-1}\equiv 1\pmod n

Most igazoljuk a 2. állítást, amely azt állítja, hogy G_n részcsoportja a (\Z/n\Z)^{\times} multiplikatív csoportnak. Mivel (\Z/n\Z)^{\times} rendje véges, ezért a 24.13. Következmény szerint elegendő azt ellenőrizni, hogy G_n nemüres és zárt a maradékosztályok közötti szorzásra, mint műveletre. Az első feltétel nyilván teljesül, hiszen 1^{p-1}\equiv 1\pmod n, és így az 1. állítás értelmében az [1]_n maradékosztály benne van G_n-ben.

Legyen most [a]_n és [b]_n két tetszőleges maradékosztály, amelyek a G_n halmaz elemei. Ez az imént bizonyított 1. állítás alapján azt jelenti, hogy teljesülnek az alábbi kongruenciák:

\begin{aligned}a^{p-1}&\equiv 1\pmod n \\ b^{p-1}&\equiv 1\pmod n\end{aligned}

A két kongruenciát a 20.2. Tétel 5. pontja alapján összeszorozhatjuk egymással, így ezt kapjuk:

a^{p-1}b^{p-1}\equiv 1\pmod n

A baloldalt a hatványozás azonosságairól szóló 18.8. Tétel 1. pontját felhasználva átírhatjuk:

(ab)^{p-1}\equiv 1\pmod n

Ez viszont ismét az imént bizonyított 1. állítás miatt azt jelenti, hogy az [ab]_n maradékosztály is a G_n halmaz eleme. Az [ab]_n maradékosztály azonban a 20.5. Tételben szereplő definíciónak megfelelően épp az [a]_n és [b]_n maradékosztályok szorzata. A G_n halmaz tehát valóban részcsoport (\Z/n\Z)^{\times}-ban.

Végül a 3. állítást igazoljuk. Azt már láttuk, hogy c=1 esetben G_n=(\Z/n\Z)^{\times}, így elegendő azt igazolni, hogy c\geq 2 esetén viszont valódi részcsoportról van szó. Azaz kell találni egy olyan redukált maradékosztályt, amely nincs benne a G_n halmazban. Más szavakkal kell találnunk egy olyan a egész számot, amely relatív prím n=p^c-hez, de amelyre a^{p-1}\ \cancel{\equiv}\ 1\pmod{p^c}. Hiszen ekkor egyrészt a 20.14. Tétel alapján [a]_n egy redukált maradékosztály, másrészt pedig a már bizonyított 1. állítás alapján [a]_n\notin G_n.

Nézzük meg először, hogy mi következik abból, ha egy a szám teljesíti a fenti kongruenciát. Ekkor ugye a (\Z/n\Z)^{\times} csoportban a 24.12. Tétel 2. pontja alapján az [a]_n maradékosztály rendje osztója p-1-nek, azaz teljesül az alábbi oszthatóság:

o([a]_n)|p-1

Ám p-1 prímtényezős felbontásában biztosan nem szerepel p, így nem szerepelhet p-1 egyetlen osztójának prímtényezős felbontásában sem, emiatt o([a]_n) felbontásában sem, azaz:

p\nmid o([a]_n)

Megfordítva a gondolatmenetet, ha tehát találunk egy olyan [a]_n redukált maradékosztályt, amelynek rendje osztható p-vel, akkor az kizárja azt, hogy teljesüljön az a^{p-1}\equiv 1\pmod{p^c} kongruencia, ami a már bizonyított 1. állítás alapján azt jelentené, hogy [a]_n\notin G_n.

Vegyük észre, hogy a [p+1]_n maradékosztály teljesíti ezt a feltételt. Egyrészt ugyanis p+1 nyilván relatív prím p-hez – azaz [p+1]_n egy redukált maradékosztály –, másrészt pedig teljesül az alábbi kongruencia:

p+1\equiv 1\pmod p

Ekkor azonban alkalmazható a 24.17. Következmény, amely szerint teljesül az alábbi kongruencia is:

(p+1)^{p^{c-1}}\equiv 1\pmod{\underbrace{p^c}_{=n}}

Ez viszont a 24.12. Tétel 2. pontja alapján azt jelenti, hogy a [p+1]_n maradékosztály rendje osztója p^{c-1}-nek. Továbbá ugyanezen tétel 5. pontja miatt ez a rend biztosan nem 1, hiszen [p+1]_n\neq [1]_n. Minthogy p^{c-1} prímtényezős felbontásában csak p szerepel, ezért ennek bármilyen 1-től különböző osztója szükségképpen osztható p-vel.

A [p+1]_n redukált maradékosztály tehát valóban nincs benne G_n-ben, és így G_n tényleg valódi részcsoportja (\Z/n\Z)^{\times}-nek, ahogyan a tétel állítja.

De mi a helyzet általános esetben?

Az előző szakaszban tehát igazoltuk, hogy prímhatványok esetén a nem Miller-Rabin-tanúk pont egy valódi részcsoportot alkotnak a (\Z/n\Z)^{\times} multiplikatív csoportban. Mint ahogy azt is láttuk, hogy általános esetben sajnos nem ez a helyzet. Szerencsére azonban a következő tételben mutatunk egy olyan valódi részcsoportot, amely egyéb redukált maradékosztályok mellett tartalmazza az összes nem Miller-Rabin-tanút. Hamarosan világossá válik, hogy ez miért olyan fontos.

24.19. Tétel:

Legyen n egy tetszőleges 1-nél nagyobb páratlan szám, amelynek legalább két egymástól különböző prímtényezője is van, azaz nem prímhatvány. Képezzük azt az e\geq 1 kitevőt és k\geq 1 páratlan számot, amelyekre teljesül az alábbi:

n-1=2^e\cdot k

Ekkor létezik legalább egy olyan j kitevő a \{0; 1;2; \ldots ; e-1\} számok között, amelyekhez külön-külön találhatók olyan x egész számok, hogy teljesül az alábbi kongruencia:

x^{2^j}\equiv -1\pmod n

Jelöljük az ilyen kitevők közül a legnagyobbat j_{\text{max}}-szal, és legyen H_n azon [a]_n maradékosztályok halmaza, amelyek esetén az a^{2^{j_{\text{max}}}k} hatvány 1-gyel vagy -1-gyel kongruens modulo n, azaz:

a^{2^{j_{\text{max}}}k} \equiv \pm 1\pmod n

Ekkor H_n-re igazak az alábbiak:

  1. A H_n halmaz minden eleme redukált maradékosztály. Másként fogalmazva H_n részhalmaza a (\Z/n\Z)^{\times} multiplikatív csoportnak, azaz H_n\sube (\Z/n\Z)^{\times}.
  2. A H_n halmaz ezen felül a (\Z/n\Z)^{\times} multiplikatív csoport egy részcsoportja, azaz H_n\leq (\Z/n\Z)^{\times}.
  3. A H_n részcsoport tartalmazza az összes NEM Miller-Rabin-tanút.
  4. A H_n egy valódi részcsoport, azaz létezik olyan modulo n redukált maradékosztály, amely nincs benne H_n-ben.

Bizonyítás:

Előszöris nyilván létezik legalább egy a tételben említett feltételnek megfelelő j kitevő, hiszen például j=0 és x=-1 választással teljesül az alábbi kongruencia:

(\underbrace{-1}_{=x})^{2^{\overbrace{0}^{=j}}}\equiv -1\pmod n

Tehát az ilyen kitevők között létezik legnagyobb is, amelyet ugye j_{\text{max}}-szal jelöltünk.

Nézzük először az 1. állítást, és mutassuk meg, hogy a H_n-ben lévő összes [a]_n maradékosztály redukált. A H_n halmaz definíciója miatt:

a^{2^{j_{\text{max}}}k} \equiv \pm 1\pmod n

Akár 1, akár -1 szerepel a jobboldalon, a kongruenciát négyzetre emelve a következőt kapjuk:

a^{2^{j_{\text{max}}+1}k} \equiv 1\pmod n

Találtunk tehát egy olyan pozitív kitevőt – nevezetesen 2^{j_{\text{max}}+1}k-t – amelyre emelve a-t az eredmény kongruens lesz 1-gyel modulo n. Ebből viszont a 20.20. Tétel alapján következik, hogy a relatív prím n-hez, azaz a 20.14. Tétel értelmében [a]_n redukált maradékosztály. Ezzel igazoltuk a tétel 1. állítását.

A 2. állítás igazolásához a 24.13. Következmény értelmében azt kell megmutatni, hogy H_n nemüres és zárt a maradékosztályok közötti szorzásra, azaz a (\Z/n\Z)^{\times} csoport műveletére nézve. Mivel 1^{2^{j_{\text{max}}}k}\equiv 1\pmod n, ezért a tétel szövege alapján H_n nemüres, hiszen tartalmazza legalább az [1]_n maradékosztályt. Legyen most [a]_n és [b]_n a H_n halmaz két tetszőleges eleme. A H_n halmaz definíciója miatt ekkor teljesülnek az alábbi kongruenciák:

\begin{aligned}a^{2^{j_{\text{max}}}k} &\equiv \pm 1\pmod n \\ b^{2^{j_{\text{max}}}k} &\equiv \pm 1\pmod n\end{aligned}

A 20.2. Tétel 5. pontja szerint ez a két kongruencia összeszorozható. Ekkor a 18.8. Tétel 1. pontjának alkalmazása után ezt kapjuk:

(ab)^{2^{j_{\text{max}}}k} \equiv \pm 1\pmod n

Azt kaptuk tehát, hogy az [ab]_n maradékosztály is a H_n halmaz eleme. Minthogy az [ab]_n maradékosztály a 20.5. Tételben bevezetett műveletek definíciója alapján épp az [a]_n és [b]_n maradékosztályok szorzata, ezért H_n zárt a (\Z/n\Z)^{\times} multiplikatív csoport műveletére nézve, azaz a 24.13. Következmény értelmében annak valóban részcsoportja. Ezzel igazoltuk a tétel 2. állítását.

A 3. állítás igazolásához tekintsünk egy tetszőleges [a]_n maradékosztályt, amely nem Miller-Rabin-tanú. Ekkor a Miller-Rabin-tanúk 23.9. Definíciója alapján vagy teljesül az a^k\equiv 1\pmod n kongruencia, vagy pedig létezik olyan j kitevő a \{0; 1;2; \ldots ; e-1\} számok között, amelyre teljesül az alábbi kongruencia:

a^{2^j\cdot k}\equiv -1\pmod n

Amennyiben az a^k\equiv 1\pmod n kongruencia teljesül, akkor mindkét oldalt j_{\text{max}}-szor négyzetre emelve, továbbá alkalmazva a 18.8. Tétel 2. pontját, az alábbit kapjuk:

a^{2^{j_{\text{max}}}k}\equiv 1\pmod n

Következésképp az [a]_n maradékosztály benne van a H_n halmazban.

Most nézzük meg, mi a helyzet akkor, ha nem teljesül az a^k\equiv 1\pmod n kongruencia. Ekkor ugye – mint már említettük – létezik olyan j kitevő a \{0; 1;2; \ldots ; e-1\} számok között, amelyre teljesül az alábbi kongruencia:

a^{2^j\cdot k}\equiv -1\pmod n

Alkalmazva a hatványozás azonosságairól szóló 18.8. Tétel 2. pontját ez így írható fel:

(a^k)^{2^j}\equiv -1\pmod n

Az a^k tehát egy olyan egész szám, amelyet a 2-nek a j-edik hatványára, mint kitevőre emelve egy olyan egész számot kapunk, amely -1-gyel kongruens modulo n. A tétel szövegében bevezetett j_{\text{max}} definíciója alapján ekkor j\leq j_{\text{max}}.

Amennyiben egyenlőség áll fenn, azaz j=j_{\text{max}}, akkor teljesül az alábbi kongruencia:

a^{2^{\overbrace{j}^{=j_{\text{max}}}}\cdot k}\equiv -1\pmod n

Ez a H_n halmaz definíciója alapján azt jelenti, hogy [a]_n\in H_n.

Amennyiben nem áll fenn egyenlőség, akkor j\lt j_{\text{max}}. Az alábbi kongruenciáról ugye már tudjuk, hogy teljesül:

(a^k)^{2^j}\equiv -1\pmod n

Mindkét oldalt sorozatosan négyzetre emelve az alábbi kongruenciákat kapjuk:

\begin{aligned}(a^k)^{2^{j+1}}&\equiv 1\pmod n \\ (a^k)^{2^{j+2}}&\equiv 1\pmod n \\ (a^k)^{2^{j+3}}&\equiv 1\pmod n \\ &\vdots \end{aligned}

Mivel j\lt j_{\text{max}}, ezért a sorozatos négyzetre emelések hatására előbb-utóbb a alábbi kongruenciát fogjuk kapni:

(a^k)^{2^{j_{\text{max}}}}\equiv 1\pmod n

Alkalmazva a hatványozás azonosságairól szóló 18.8. Tétel 2. pontját ez így írható fel:

a^{2^{j_{\text{max}}}k}\equiv 1\pmod n

Ez a H_n halmaz definíciója alapján ugyancsak azt jelenti, hogy [a]_n\in H_n. Igazoltuk tehát a tétel 3. állítását, miszerint minden nem Miller-Rabin-tanú a H_n részcsoportban van.

Végül a 4. állításhoz azt kell igazolni, hogy H_n valódi részcsoport (\Z/n\Z)^{\times}-ben, azaz találni kell egy olyan redukált maradékosztályt, amely nincs benne H_n-ben. Az n-ről a tétel szövegében kikötöttük, hogy ő egy olyan 1-nél nagyobb páratlan összetett szám, amelynek legalább két egymástól különböző prímtényezője van. Legyen n egyik prímtényezője p. Ekkor létezik olyan c\geq 1 kitevő és m\gt 1 páratlan egész szám, hogy egyrészt m tovább már nem osztható p-vel, másrészt pedig n felírható az alábbi alakban:

n=p^cm

A 24.15. Definíció alapján úgy is mondhatjuk, hogy az n egész szám p-adikus rendje c\geq 1.

Ekkor p^c-nek és m-nek nincs közös prímtényezője, mert ha lenne, akkor az csak p valamilyen nulladiknál nagyobb hatványa lehetne, és így az n egész szám p-adikus rendje biztosan nagyobb lenne c-nél. Így tehát p^c és m relatív prímek. Ebben az esetben érvényes a kínai maradéktétel (22.2. Tétel), amelynek következményeként a 22.8. Tétel alapján fennáll az alábbi gyűrűizomorfizmus:

\Z/n\Z \simeq \Z/p^c\Z \times \Z/m\Z

A tétel szövegéből tudjuk, hogy a j_{\text{max}} kitevőhöz létezik olyan egész szám, amelyet x helyére behelyettesítve teljesül az alábbi kongruencia:

x^{2^{j_{\text{max}}}}\equiv -1\pmod n

Jelöljük az egyik ilyen egész számot s-sel, és tekintsük az [s]_n maradékosztályt a \Z/n\Z gyűrűben. Neki a 22.8. Tételben szereplő g gyűrűizomorfizmus az alábbi maradékosztálypárt felelteti meg a \Z/p^c\Z \times \Z/m\Z gyűrűben:

[s]_n \xmapsto{g} ([s]_{p^c};[s]_m)

Ha a baloldali [s]_n maradékosztályt a 2^{j_{\text{max}}}k-adik hatványra emeljük a \Z/n\Z gyűrűben, akkor a g gyűrűizomorfizmus a művelettartó tulajdonság miatt ehhez épp a jobboldali maradékosztálypárnak a \Z/p^c\Z \times \Z/m\Z gyűrűben vett 2^{j_{\text{max}}}k-adik hatványát fogja hozzárendelni. Azaz:

[s]_n^{2^{j_{\text{max}}}k} \xmapsto{g} ([s]_{p^c};[s]_m)^{2^{j_{\text{max}}}k}

A jobboldalon szereplő szorzatgyűrűbeli szorzást – és így a hatványozást – a 22.7. Tétel alapján komponensenként kell elvégezni, azaz:

[s]_n^{2^{j_{\text{max}}}k} \xmapsto{g} ([s]_{p^c}^{2^{j_{\text{max}}}k};[s]_m^{2^{j_{\text{max}}}k})

A maradékosztályok közötti szorzást – és így a hatványozást – viszont a 20.5. Tétel szerint a reprezentánselemeken kell elvégezni, azaz:

[s^{2^{j_{\text{max}}}k}]_n \xmapsto{g} ([s^{2^{j_{\text{max}}}k}]_{p^c};[s^{2^{j_{\text{max}}}k}]_m)

A baloldalon szereplő modulo n maradékosztály reprezentánseleme tehát s^{2^{j_{\text{max}}}k}, amely a hatványozás azonosságairól szóló 18.8. Tétel 2. pontja alapján (s^{2^{j_{\text{max}}}})^k-val egyezik meg. Az s definíciójából tudjuk azonban, hogy:

s^{2^{j_{\text{max}}}}\equiv -1\pmod n

Mindkét oldalt k-adik hatványra emelve a kongruencia jobboldalán továbbra is -1 marad, hiszen k a tétel szövege alapján páratlan:

s^{2^{j_{\text{max}}}k}\equiv \underbrace{-1}_{=(-1)^k}\pmod n

Vagyis a fenti g szerinti hozzárendelés baloldalán tulajdonképpen a [-1]_n maradékosztály szerepel. Ám ekkor a g gyűrűizomorfizmus 22.8. Tételben szereplő definíciója alapján a jobboldalon pedig a ([-1]_{p^c};[-1]_m) maradékosztálypár kell szerepeljen:

\underbrace{[s^{2^{j_{\text{max}}}k}]_n}_{=[-1]_n} \xmapsto{g} (\underbrace{[s^{2^{j_{\text{max}}}k}]_{p^c}}_{=[-1]_{p^c}};\underbrace{[s^{2^{j_{\text{max}}}k}]_m}_{=[-1]_m})

Vagyis azt kaptuk, hogy az s^{2^{j_{\text{max}}}k} hatvány -1-gyel kongruens modulo p^c is, azaz:

s^{2^{j_{\text{max}}}k}\equiv -1\pmod{p^c}

Ezt a kongruenciát hamarosan felhasználjuk, amikoris a g gyűrűizomorfizmus segítségével megmutatjuk, hogy létezik olyan X\in \Z/n\Z redukált maradékosztály, amely nincs benne H_n-ben. A H_n definíciója alapján ez a keresett X maradékosztály pontosan akkor nincs benne H_n-ben, ha az ő \Z/n\Z gyűrűben vett 2^{j_{\text{max}}}k-adik hatványa különbözik mind az [1]_n, mind pedig a [-1]_n maradékosztálytól.

Legyen ez a keresett X az a maradékosztály, amely esetén a g gyűrűizomorfizmus épp az alábbi hozzárendelést valósítja meg:

X \xmapsto{g} ([s]_{p^c};[1]_m)

Ilyen X ugye létezik, hiszen g kölcsönösen egyértelmű leképezés, azaz minden \Z/p^c\Z \times \Z/m\Z-beli maradékosztálypárt hozzárendeli valamelyik \Z/n\Z-beli maradékosztályhoz – jelen esetben az ([s]_{p^c};[1]_m) párt X-hez. A g művelettartó tulajdonsága alapján ekkor teljesül az alábbi hozzárendelés is:

X^{2^{j_{\text{max}}}k} \xmapsto{g} ([s]_{p^c};[1]_m)^{2^{j_{\text{max}}}k}

A jobboldalon szereplő szorzatgyűrűbeli szorzást – és így a hatványozást – a 22.7. Tétel alapján komponensenként kell elvégezni, azaz:

X^{2^{j_{\text{max}}}k} \xmapsto{g} ([s]_{p^c}^{2^{j_{\text{max}}}k};[1]_m^{2^{j_{\text{max}}}k})

A maradékosztályok közötti szorzást – és így a hatványozást – viszont a 20.5. Tétel szerint a reprezentánselemeken kell elvégezni, azaz:

X^{2^{j_{\text{max}}}k} \xmapsto{g} ([s^{2^{j_{\text{max}}}k}]_{p^c};[\underbrace{1^{2^{j_{\text{max}}}k}}_{=1}]_m)

Azt azonban már tudjuk, hogy teljesül az alábbi kongruencia:

s^{2^{j_{\text{max}}}k}\equiv -1\pmod{p^c}

Így tehát a fenti g szerinti hozzárendelés valójában az alábbi:

X^{2^{j_{\text{max}}}k} \xmapsto{g} ([-1]_{p^c};[1]_m)

Így viszont a baloldalon szereplő X^{2^{j_{\text{max}}}k} hatvány biztosan nem lehet az [1]_n maradékosztály. Ebben az esetben ugyanis a g gyűrűizomorfizmus a 22.8. Tétel alapján az alábbi hozzárendelést valósítaná meg:

\underbrace{[1]_n}_{=X^{2^{j_{\text{max}}}k}} \xmapsto{g} \underbrace{([1]_{p^c};[1]_m)}_{=([-1]_{p^c};[1]_m)}

Ez csak akkor volna lehetséges, ha [1]_{p^c}=[-1]_{p^c} teljesülne, azaz fennállna az alábbi kongruencia:

1\equiv -1\pmod{p^c}

Ez viszont azt jelentené, hogy teljesül az alábbi oszthatóság:

p^c|\underbrace{1-(-1)}_{=2}

Ez viszont lehetetlen, hiszen p az n prímtényezője, amely páratlan, ezért p is, és így p^c is páratlan, azaz legalább 3. Márpedig a 17.2. Lemma alapján egy pozitív egész szám bármely osztója legfeljebb akkora lehet, mint maga a szám.

Hasonló gondolatmenet alapján az X^{2^{j_{\text{max}}}k} hatvány biztosan nem lehet a [-1]_n maradékosztály sem, hiszen ekkor a g gyűrűizomorfizmus a 22.8. Tétel alapján az alábbi hozzárendelést valósítaná meg:

\underbrace{[-1]_n}_{=X^{2^{j_{\text{max}}}k}} \xmapsto{g} \underbrace{([-1]_{p^c};[-1]_m)}_{=([-1]_{p^c};[1]_m)}

Ez csak akkor volna lehetséges, ha [-1]_m=[1]_m teljesülne, azaz fennállna az alábbi kongruencia:

1\equiv -1\pmod m

Ez viszont azt jelentené, hogy teljesül az alábbi oszthatóság:

m|\underbrace{1-(-1)}_{=2}

Ez viszont ugyancsak lehetetlen, hiszen m-ről azt mondtuk, hogy 1-nél nagyobb páratlan egész, azaz legalább 3.

Azt kaptuk tehát, hogy az X maradékosztály 2^{j_{\text{max}}}k-adik hatványa különbözik az [1]_n és [-1]_n maradékosztályoktól, és így valóban nem lehet H_n-ben.

Annyit kell még igazolni, hogy X redukált maradékosztály, és ennek ellenére nincs H_n-ben – azt ugyanis már az 1. állításban igazoltuk, hogy nem redukált maradékosztályok amúgysem lehetnek benne H_n-ben. Az X konstrukciója alapján a g gyűrűizomorfizmus ugye az alábbi hozzárendelést valósítja meg:

X \xmapsto{g} ([s]_{p^c};[1]_m)

Most tegyük fel, hogy az a egész szám az X maradékosztály egy reprezentánseleme, azaz legyen X=[a]_n. A 22.8. Tétel alapján azonban teljesül az alábbi hozzárendelés is:

\underbrace{[a]_n}_{=X} \xmapsto{g} ([a]_{p^c};[a]_m)

Mivel a g által megvalósított hozzárendelés kölcsönösen egyértelmű, ezért a fenti két hozzárendelés egyszerre csak akkor teljesülhet, ha a jobboldalakon szereplő két maradékosztálypár egy és ugyanaz, azaz fennállnak a maradékosztályok közötti alábbi egyenlőségek:

\begin{aligned}[a]_{p^c}&=[s]_{p^c} \\ [a]_m&=[1]_m\end{aligned}

A második egyenlőségből a 20.14. Tétel alapján következik, hogy a relatív prím m-hez. Az [a]_m=[1]_m maradékosztály ugyanis nyilván invertálható a \Z/m\Z gyűrűben, hiszen ő ennek a gyűrűnek az egységeleme, amelynek inverze önmaga.

Az első egyenlőségből szintén a 20.14. Tétel alapján következik, hogy a pontosan akkor relatív prím p^c-hez, ha s is az, hiszen ők ugyanannak a modulo p^c maradékosztálynak a reprezentánselemei. Az s-ről azonban korábban már megmutattuk, hogy teljesül rá az alábbi kongruencia:

s^{2^{j_{\text{max}}}k}\equiv -1\pmod{p^c}

A 20.2. Tétel 8. pontja alapján mindkét oldalt négyzetre emelhetjük:

s^{2^{j_{\text{max}}+1}k}\equiv 1\pmod{p^c}

Találtunk tehát egy olyan pozitív kitevőt – nevezetesen 2^{j_{\text{max}}+1}k-t – amelyre emelve s-t az eredmény kongruens lesz 1-gyel modulo p^c. Ebből viszont a 20.20. Tétel alapján következik, hogy s relatív prím p^c-hez, és így a is.

Egyrészt azt kaptuk tehát, hogy a relatív prím m-hez, vagyis nincs vele közös prímtényezője. Másrészt a relatív prím p^c-hez is, tehát vele sincs közös prímtényezője. Ekkor viszont a p^cm=n szorzattal sincs közös prímtényezője, tehát n-hez is relatív prím. Vagyis a 20.14. Tétel szerint az X=[a]_n valóban egy redukált maradékosztály a \Z/n\Z gyűrűben.

A Miller-Rabin-tanúk száma

Az előző két szakaszban igazolt két tétel következményeként most már könnyedén tudunk alsó becslést adni a Miller-Rabin-tanúk számára vonatkozóan.

24.20. Következmény:

Legyen n\gt 1 egy tetszőleges páratlan egész szám. Ha n összetett, akkor a modulo n redukált maradékosztályoknak legalább a fele Miller-Rabin-tanú.

Bizonyítás:

1. eset: n valamilyen prímhatvány

Ekkor tehát n=p^c, ahol p valamilyen páratlan prímszám, továbbá c\geq 2, máskülönben n=p nem lenne összetett. A 24.18. Tétel 2. és 3. pontjai alapján a nem Miller-Rabin-tanúk G_n-nel jelölt halmaza egy valódi részcsoportot alkot a (\Z/n\Z)^{\times} multiplikatív csoportban. A Lagrange-tétel (24.8. Tétel) alapján a G_n részcsoport rendje osztója a (\Z/n\Z)^{\times} csoport rendjének. Minthogy G_n valódi részcsoport, ezért ez alapján az elemeinek a száma legfeljebb feleannyi, mint a (\Z/n\Z)^{\times} csoport elemeinek a száma. A redukált maradékosztályoknak tehát legfeljebb a fele lehet nem Miller-Rabin-tanú. Másként fogalmazva legalább a felük Miller-Rabin-tanú kell legyen.

2. eset: n nem prímhatvány, azaz legalább két prímtényezője van.

Ekkor a nem Miller-Rabin-tanúk ugyan nem alkotnak részcsoportot (\Z/n\Z)^{\times}-ben, azonban a 24.19. Tétel alapján létezik olyan H_n-nel jelölt valódi részcsoport, amely viszont minden nem Miller-Rabin-tanút tartalmaz. Azaz a következő a helyzet:

A Hn részcsoport elhelyezkedése
A H_n részcsoport elhelyezkedése

Ismét a Lagrange-tétel (24.8. Tétel) miatt a redukált maradékosztályoknak legfeljebb a fele – köztük az összes nem Miller-Rabin-tanú – tartozhat H_n-be. Következésképp ebben az esetben is legalább a felük Miller-Rabin-tanú.

Hasonlítsuk össze ezt az állítást a Fermat-tanúk számára vonatkozó 23.6. Tétel állításával. Ott mindössze annyit állítottunk, hogy ha n-hez létezik Fermat-tanú, akkor a redukált maradékosztályoknak legalább a fele az. Ez tehát nem minden összetett n-re érvényes, hanem csak azokra, amelyekhez létezik Fermat-tanú. A 23.7. Definícióban ismertetett Carmichael-számok például olyan összetett számok, amelyekhez egyáltalán nincsen Fermat-tanú.

Ezzel szemben az imént bizonyított állítás minden összetett n-re érvényes, azaz Miller-Rabin-tanúja minden összetett számnak van, méghozzá – ahogy láttuk – eléggé sok. Így a Miller-Rabin-prímtesztre nézve valóban nem léteznek univerzális álprímek.

Ebben a részben tehát megismerkedtünk az absztrakt algebra egy igen hatékony eszköztárának, az úgynevezett csoportelméletnek az alapjaival. Bevezettük a csoport és a részcsoport fogalmát, továbbá definiáltuk, hogy mit értünk egy csoport illetve egy csoportelem rendje alatt. Ezután a mellékosztály fogalmának segítségével igazoltuk Lagrange tételét, amely egy fontos oszthatósági kapcsolatot mond ki egy csoport és a részcsoportok illetve csoportelemek rendjei között. Végül ezt felhasználva megmutattuk, hogy bármilyen páratlan összetett szám esetén a redukált maradékosztályoknak legalább a fele Miller-Rabin-tanú. Azaz erre a tesztre nézve nem léteznek univerzális álprímek, így gyakorlatilag szinte nincs esélye annak, hogy tévedjen.

A következő részben egy kicsit mélyebb módszerekkel azt fogjuk igazolni, hogy valójában még jobb a helyzet, és a redukált maradékosztályoknak nemhogy a fele, de legalább a háromnegyede Miller-Rabin-tanú. Ehhez a csoporthomomorfizmus fogalmával, valamint a Carmichael-számok néhány fontos tulajdonságával fogunk megismerkedni. Ezzel befejezzük számelméleti vizsgálatainkat, és a cikksorozat lezárásaként adunk némi ízelítőt abból, hogy mi vár Alice-ra és Bob-ra a – nem is olyan távoli – jövőben.

Folytatás hamarosan…

Kapcsolódó oldal:
Érintő - Elektronikus Matematikai Lapok

Vélemény, hozzászólás?

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük