Alice és Bob komolyabb fegyverekhez nyúl

24.1A 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 bambán elvégzi a képlet által leírt műveletsorozatot, és varázslatos módon megkapja a végeredményt.

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.

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.

A harmad- és negyedfokú egyenletek megoldóképleteit a XVI. század elején fedezték fel itáliai matematikusok. 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 csupán 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 fontos eszközévé vált, és nem mellesleg választ adott egy sor egyéb, addig megoldatlan problémára.

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 Felix Christian 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 is 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.

24.2Csoportelmé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, amelyeknek e művelet meg kell feleljen.

Például az egész számok \Z halmaza a szokásos összeadásra nézve Abel-csoportot alkot. Ebben a csoportban a nullelem a 0 egész szám, egy a egész szám ellentettje pedig -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 – méghozzá 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 azonban már csoportot alkot a szorzásra nézve is, amely ráadásul szintén egy Abel-csoport. Az Olvasó könnyedén leellenőrizheti, hogy erre a halmazra valóban teljesülnek a 24.1. Definícióban szereplő csoportaxiómák.

Az iménti példához hasonlóan tetszőleges (R,+,\cdot) gyűrű esetén általánosságban is beszélhetünk két speciális csoportról. Mindkettőnek az elemei a gyűrű R alaphalmazából kerülnek ki, azonban a csoportművelet az egyikük esetén a +, másikuk esetén pedig a \cdot művelet lesz. Ezeknek az R gyűrűből származtatott csoportoknak speciális nevük is van, és a 24.3. Tételben fogjuk majd definiálni őket pontosan.

Előbb azonban ismerkedjünk meg egy fontos összefüggéssel, amely két elem inverzei és a szorzatuk inverze között teremt kapcsolatot. A tételt teljes általánosságban, azaz nem kimondottan csoportokra fogalmazzuk meg.

Most vizsgáljuk meg, hogy pontosan hogyan tudjuk a fentebb már említett két speciális csoportot származtatni tetszőleges gyűrűből. Ennek során újabb fontos, gyűrűkel kapcsolatos csoportelméleti fogalmakkal is megismerkedünk.

Az iménti tétel 2. állítása alapján tehát egy egységelemes gyűrű invertálható elemei csoportot alkotnak a gyűrű szorzására nézve. Számunkra ebben a fejezetben 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.

Látható, hogy valóban minden elemnek létezik inverze, hiszen minden sorban szerepel az [1]_{10} maradékosztály, amely tehát a (\Z/10\Z)^{\times} csoport neutrális eleme. 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.

24.3Ré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.

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ó szerinti 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.4Lagrange 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ázzunk egy fontos fogalmat.

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. Igazoljuk továbbá, hogy ez egy ekvivalenciareláció, amely a 13.6. Tétel értelmében 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 bizonyítása utáni megjegyzésben bővebben is kitérünk.

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 23.5. szakaszban bemutatott 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.

Bizonyítás:

A bizonyításhoz 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 láttuk, hogy az ott 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.6. 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 úniójuk a teljes G. Ez az elrendezés látható a 24.1. ábrán.

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 elemei és a H részcsoport elemei között.

A 24.7. Tétel bizonyítása után 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, amely az alábbi két állítást jelenti:

1. Tetszőleges x\in gH és y\in gH esetén ha f(x)=f(y), akkor 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 hozzárendeli.

Az 1. állítás: 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 G egységelemét:

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

Ez viszont a 3. csoportaxióma értelmében épp a kívánt x=y egyenlőség.

A 2. állítás: Ehhez keresnünk kell egy olyan x\in gH elemet, amelyhez az f függvény épp a h\in H elemet rendeli hozzá. Tehát az alábbi egyenlet megoldását keressük:

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

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

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

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

Összefoglalva: 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ó a 24.2. ábrán.

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 – mivel ezek a baloldali mellékosztályok G egy partícióját alkotják – épp G rendjét kapjuk eredményül. A 16.1. Definíció értelmében ez azt jelenti, hogy |H| osztója |G|-nek.

Megnézem a tudásbázisban→

∎

24.5Negatív kitevős hatványok

A 23.8. szakaszban 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 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 két másik olyan felhasználónak is elküld, akik azonos modulust használnak.

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 a 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 hatványozás alatt – rendelkezik neutrális elemmel és invertálható. Az alábbi definícióban ezt teljes általánosságban fogalmazzuk meg.

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. Ehhez szükségünk lesz egy segédtételre.

Ebből már igazolhatjuk a 18.8. Tétel kiterjesztését az egész kitevős hatványozásra.

Í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.15. 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 kiszámíthatja az m és y_1 vagy y_2 kitüntetett közös osztóját, tehát végülis m egyik prímtényezőjét. Ebből azonnal megkapja a másik prímtényezőt, és ezek birtokában ő is előállíthatja a titkos kulcsot. Sőt, ugyanezt maga a küldő fél is megteheti, hiszen ugye már 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 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 nem sokkal 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.

24.6Csoportelem 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.

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 minket egy fontos fogalomhoz, amelyet az alábbi definícióban tetszőleges csoportra – tehát nem kizárólag a maradékosztálygyűrűk multiplikatív csoportjaira – fogalmazunk meg.

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

A 24.3. szakaszban szó volt róla, hogy hogyan lehet könnyen ellenőrizni azt, hogy egy G csoport valamely H részhalmaza részcsoportot alkot-e G-ben, 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 inverzké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.

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.7A Miller-Rabin-nemtanúk fedőcsoportja

Ennyi csoportelméleti bevezető után most térjünk vissza az eredeti problémánkra, és próbáljunk meg egy alsó becslést adni a Miller-Rabin-tanúk számára. Ezzel egyúttal azt is meg fogjuk mutatni, hogy a Miller-Rabin prímteszt elől a Carmichael-számok sem tudnak elbújni.

A bemenetünk tehát egy n\gt 1 páratlan egész szám, amelyről el kéne dönteni, hogy prím-e vagy összetett, a vizsgálatunk tárgya pedig a 24.3. Tétel szerinti (\Z/n\Z)^{\times} multiplikatív csoport, amely ugye a modulo n redukált maradékosztályokból áll. A 23.9. Definíció, valamint a hozzá kapcsolódó megjegyzés alapján ugyanis az összes Miller-Rabin-tanú és az összes Miller-Rabin-nemtanú ebben a csoportban helyezkedik el, továbbá együtt le is fedik az egész csoportot, mivel minden redukált maradékosztály pontosan az egyik kategóriába tartozik.

A stratégiánk központi eleme a Lagrange-tétel lesz, amely szerint (\Z/n\Z)^{\times} bármely részcsoportjának az elemszáma osztója (\Z/n\Z)^{\times} elemszámának. Elsődleges célunk tehát az lesz, hogy keressünk egy olyan részcsoportot (\Z/n\Z)^{\times}-ben, amely tartalmazza az összes Miller-Rabin-nemtanút. Ezt a részcsoportot H_n-nel, a Miller-Rabin-nemtanúk halmazát pedig G_n-nel fogjuk jelölni a továbbiakban. Ezután azt kell megmutatnunk, hogy H_n valódi részcsoport, ekkor ugyanis a Lagrange-tétel miatt ennek a részcsoportnak az elemszáma legfeljebb feleannyi lehet, mint a teljes (\Z/n\Z)^{\times} csoport elemszáma. Mármost ha H_n valóban tartalmazza az összes Miller-Rabin-nemtanút – azaz G_n\sube H_n –, akkor abból következik, hogy G_n az összes redukált maradékosztályoknak "még inkább" legfeljebb csak a felét teheti ki. Másként fogalmazva: a redukált maradékosztályoknak legalább a fele Miller-Rabin-tanú kell legyen.

A keresett H_n részcsoport konstrukciójához induljunk ki a 23.9. Definícióból. Itt ugye n páratlan, ezért n-1 páros, és így ő felírható 2^ek alakban valamilyen e\geq 1 egész kitevővel és k\geq 1 páratlan számmal. Ezután véletlenszerűen kiválasztunk egy [a]_n redukált maradékosztályt, és elkezdjük sorra megvizsgálni, hogy az a^k, majd az ebből sorozatos négyzetreemelésekkel kapott a^{2k}, a^{2^2k}, a^{2^3k}, ..., a^{2^{e-1}k} hatványok mivel kongruensek modulo n.

A különböző lehetséges forgatókönyveket a táblázatban vízszintes vonalakkal választottuk el egymástól. Az első kategóriába az összes Miller-Rabin-nemtanú került, amely ugye a G_n halmaz. Ezeknél tehát az a^k-tól induló négyzetreemelési lánc vagy csupa +1 értéket ad, vagy pedig legfeljebb e-1 lépésben elérik a -1 értéket. A táblázatban egy felfele mutató nyíllal megjelöltük azt a "kritikus szintet", amikorra már mindegyik Miller-Rabin-nemtanú "lebukott": vagy már beleesett a +1-es "csapdába", vagy pedig elérte a -1-et, és menthetetlenül bele fog esni.

A további redukált maradékosztályok már mind Miller-Rabin-tanúk, azaz a G_n halmazon kívül vannak. A táblázat második kategóriájában ezek közül azok szerepelnek – például a [14]_{65} és az [51]_{65} –, amelyek legkésőbb a "kritikus szintet" elérve már szintén bekerültek ebbe a "csapdába", ám ezt a -1 kihagyásával tették. A harmadik kategóriában lévő Miller-Rabin-tanúk – például a [12]_{65} és a [21]_{65} – ugyancsak a -1 kihagyásával estek "csapdába", ám ezt a "kritikus szint" után tették csak meg. Végül a negyedik kategóriában lévő Miller-Rabin-tanúk – például a [2]_{65} és a [3]_{65} – egyáltalán nem estek "csapdába" e-1 lépés alatt sem.

Az látszik, hogy a keresett H_n részcsoport a G_n halmaznál általában bővebb. A fenti példában szereplő [8]_{65} és [18]_{65} redukált maradékosztályok például mindketten G_n-ben vannak, ám az ő szorzatuk a [14]_{65} redukált maradékosztály, ami viszont már Miller-Rabin-tanú. Tehát a G_n halmaz nem zárt a maradékosztályok szorzására, mint műveletre nézve, és így részcsoport sem lehet.

Vegyük észre azonban, hogy a [14]_{65} redukált maradékosztály még mindig speciális abban az értelemben, hogy a "kritikus szintig" bezárólag ő is "csapdába" esett a +1-ben. A különbség mindössze annyi, hogy ő ezt nem a -1-en keresztül tette meg, hanem közvetlenül, és pusztán emiatt nem lehet ő benne G_n-ben a 23.9. Definíció értelmében. Most megmutatjuk, hogy ha a G_n halmazhoz hozzávesszük a "kritikus szintig" bezárólag bármilyen okból "csapdába" eső redukált maradékosztályokat is, akkor az így kapott halmaz már részcsoportot alkot.

Az alábbi tétel megfogalmazása bonyolultnak tűnik, ám pusztán az iménti gondolatokat önti precíz matematikai formába.

Végül megmutatjuk, hogy H_n valóban minden Miller-Rabin-nemtanút tartalmaz.

24.8A Miller-Rabin-tanúk száma

A prímhatvány esethez – azaz amikor n=p^c valamilyen p\gt 1 páratlan prímszám és c\gt 1 kitevő esetén – szükségünk lesz két segédtételre. Az elsőben egy egyszerű, hatványkülönbségekkel kapcsolatos algebrai összefüggést igazolunk, majd megvizsgáljuk az 1+p szám hatványait modulo p^2.

Ez a segédtétel egyébként majd a 26.7. szakaszban, a Carmichael-számok vizsgálatakor is hasznos lesz még számunkra.

Most már minden készen áll annak bizonyításához, hogy prímhatvány esetben a 24.16. Tételben definiált H_n egy valódi részcsoport.

A nem prímhatvány esethez alapvetően a 22.7. Tétel szerinti gyűrűizomorfizmus segítségével szeretnénk megkonstruálni egy olyan redukált maradékosztályt, amely nincs benne H_n-ben. Ehhez azonban szükségünk van az alábbi egyszerű állításra, amely ennek a konstrukciónak a kulcsa lesz.

Most mutatunk egy olyan redukált maradékosztályt, amely nincs benne H_n-ben, és amely ráadásul Fermat-nemtanú. Ez utóbbinak a 26. fejezetben szintén nagy hasznát fogjuk venni, amikor kicsit mélyebb csoportelméleti eszközök segítségével a Miller-Rabin-tanúk számára vonatkozó mostani becslésünket fogjuk tovább javítani.

Összefoglalva tehát: ha n egy páratlan összetett szám, akkor a Miller-Rabin-nemtanúk a 24.17. Tétel alapján mindannyian benne vannak a 24.16. Tétel szerinti H_n részcsoportban. Ez prímhatvány esetben a 24.20. Tétel miatt, egyéb esetekben pedig a 24.22. Tétel 3. és 4. pontja miatt ráadásul egy valódi részcsoport (\Z/n\Z)^{\times}-ben. Ennek következményeként a Lagrange-tétel segítségével most már könnyedén tudunk alsó becslést adni a Miller-Rabin-tanúk számára vonatkozóan.

Bizonyítás:

Először is a 23.9. Definíció értelmében (\Z/n\Z)^{\times} minden eleme vagy Miller-Rabin-tanú, vagy Miller-Rabin-nemtanú. Elegendő tehát azt megmutatnunk, hogy (\Z/n\Z)^{\times} elemeinek legfeljebb a fele Miller-Rabin-nemtanú.

A 24.17. Tételnek megfelelően jelölje G_n az n Miller-Rabin-nemtanúinak halmazát, H_n pedig a 24.16. Tételben bevezetett részcsoportot (\Z/n\Z)^{\times}-ben. Ekkor a 24.17. Tétel szerint G_n\sube H_n. A H_n részcsoport prímhatvány esetben a 24.20. Tétel miatt, egyéb esetekben pedig a 24.22. Tétel 3. és 4. pontja miatt egy valódi részcsoport. Azaz:

G_n\sube H_n\lt (\Z/n\Z)^{\times}

Ezt a szituációt mutatja a 24.3. ábra.

A Lagrange-tétel szerint H_n rendje osztója a (\Z/n\Z)^{\times} csoport rendjének, azaz teljesül az alábbi összefüggés, ahol r a H_n részcsoport indexe (\Z/n\Z)^{\times}-ben:

r\cdot |H_n| = |(\Z/n\Z)^{\times}|

Mivel H_n valódi részcsoport, ezért |H_n|\lt |(\Z/n\Z)^{\times}|, így r\geq 2. Igaz tehát az alábbi egyenlőtlenség:

2\cdot |H_n|\leq |(\Z/n\Z)^{\times}|

Továbbá a 24.17. Tétel miatt G_n\sube H_n, ezért |G_n|\leq |H_n|, és így:

2\cdot |G_n|\leq 2\cdot |H_n|

A két egyenlőtlenséget összevetve megkapjuk a tétel állítását:

2\cdot |G_n|\leq |(\Z/n\Z)^{\times}

Azaz a redukált maradékosztályoknak legfeljebb a fele lehet Miller-Rabin-nemtanú. Másként fogalmazva legalább a felük Miller-Rabin-tanú kell legyen.

Megnézem a tudásbázisban→

∎

Hasonlítsuk össze ezt az állítást a Fermat-tanúk számára vonatkozó a 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 egyáltalán létezik Fermat-tanú. A Carmichael-számok épp azok az összetett számok, amelyekhez egyáltalán nem létezik Fermat-tanú.

Ezzel szemben az imént bizonyított állítás minden páratlan összetett n-re érvényes. Így a 23.5. szakaszban ismertetett Miller-Rabin prímteszt elől valóban nem bújhatnak el még a Carmichael-számok sem.