Legyen tetszőleges csoport, ennek valamely eleme, pedig az egységelem. Ha rendje véges, akkor tetszőleges és egész számok esetén igazak az alábbiak: akkor és csak akkor teljesül, ha fennáll az oszthatóság, ami a 3. pontja alapján …
Legyen tetszőleges véges csoport, pedig tetszőleges részcsoport -ben. Ekkor a részcsoport rendje osztója rendjének, azaz teljesül az alábbi oszthatóság: Azaz létezik olyan egész szám, amellyel rendjét megszorozva épp rendjét kapjuk. Ez az egész szám a …
Legyen tetszőleges csoport, pedig valamilyen részcsoport -ben. Definiáljunk egy szimbólummal jelölt relációt a csoport elemei között a következőképpen: akkor és csak akkor, ha . Ekkor a reláció egy ekvivalenciareláció a csoport elemei között. Az ehhez …
Legyen egy pozitív prímszám, pedig egy tetszőleges egész szám, amely -vel osztva -et ad maradékul, azaz amelyre teljesül az alábbi kongruencia: Ekkor tetszőleges egész kitevő esetén teljesül az alábbi kongruencia is:
Egy tetszőleges csoport valamely részhalmaza akkor és csak akkor részcsoport -ben, ha teljesülnek az alábbi feltételek: zárt a csoport műveletére. tartalmazza a csoport egységelemét. zárt a -beli inverzképzésre.
Legyen egy tetszőleges halmaz, amelyen értelmezve van egy -gal jelölt asszociatív művelet, és tegyük fel, hogy létezik -ban neutrális elem () erre a műveletre nézve. Legyenek továbbá és a halmaz két olyan eleme, amelyek invertálhatók …
Legyen tetszőleges halmaz, amelyen értelmezve van egy 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 és a két invertálható eleme. Ekkor tetszőleges – …
Legyen tetszőleges csoport, pedig ennek valamely eleme. Ekkor egymástól különböző hatványainak a számát rendjének nevezzük, és az angol „order” kifejezésre utalva -vel jelöljük. Ha -nek végtelen sok különböző hatványa létezik a csoportban, akkor azt mondjuk, …
Egy csoport rendje alatt a benne lévő elemek számát értjük. Pontosabban fogalmazva ha csak véges sok elemet tartalmaz, és elemeinek száma , akkor azt mondjuk, hogy véges, és rendje . Ezt így jelöljük: . Ezzel …
A -ban szereplő gyűrűaxiómák a ban ismertetett félcsoport és csoport fogalmának segítségével átfogalmazhatók. Eszerint tegyük fel, hogy adva van egy halmaz, amelyen értelmezve van egy -szal és egy -tal jelölt kétváltozós művelet. Az algebrai struktúrát …
Legyen egy tetszőleges nemnulla egész szám, pedig valamilyen pozitív prímszám. Azt mondjuk, hogy az egész szám -adikus rendje (ennek jele: ), amennyiben igazak az alábbiak: A egész szám -adikus rendjét végtelennek definiáljuk, azaz .
Ha egy csoport valamely részhalmaza maga is csoport a műveletére nézve, akkor azt mondjuk, hogy részcsoport -ben. Ezt így jelöljük: . Ha részcsoport -ben, de , akkor azt mondjuk, hogy valódi részcsoport -ben. Ezt így …
Legyen tetszőleges halmaz, amelyen értelmezve van egy -gal jelölt asszociatív művelet. Ha a halmaz valamely eleme, pedig tetszőleges pozitív egész, akkor az hatványon az alábbi kifejezést értjük: Tegyük fel, hogy a műveletre nézve létezik neutrális …
Tegyük fel, hogy adva van egy valamilyen halmaz, amelyen értelmezve van egy kétváltozós művelet. Nevezzük ezt a műveletet szorzásnak és jelöljük -tal, vagy egymás után írással. Például egy és egy elem szorzatát jelöljük -vel vagy …
Hogyan képes Alice és Bob az RSA-kulcsgeneráláshoz szükséges többszázjegyű prímszámokat találni? Hogyan tudják ezt megtenni anélkül, hogy az idők végezetéig osztáspróbákat kellene végezniük? Mik azok a prímtesztek, és pontosan hogyan működnek? Mely számokat nevezzük univerzális álprímeknek, és hogyan tudunk megszabadulni tőlük?
A Fermat-tanú jához hasonlóan itt is teljes maradékosztályokra célszerű vonatkoztatni ezt a fogalmat. Ha ugyanis egy egész szám -val azonos modulo maradékosztályban van, akkor teljesül az kongruencia, és így a 8. pontja alapján teljesülnek az …
A definícióban nem kell külön kikötni, hogy és legyen relatív prím – ami a értelmében azt jelentené, hogy egy redukált maradékosztály –, hiszen ha nem ez lenne a helyzet, akkor az szintén tanúsítaná összetettségét. Ez …
Legyen egy tetszőleges páratlan prímszám, továbbá legyen adva egy tetszőleges redukált maradékosztály. Képezzük azt az kitevőt és páratlan számot, amelyekre teljesülnek az alábbiak: Azt kell igazolni, hogy nem lehet Miller-Rabin-tanú, azaz az alábbi kongruenciák közül …
Azt a jól ismert azonosságot fogjuk használni, miszerint bármilyen kommutatív gyűrű tetszőleges és elemeire teljesül az alábbi: Ez a ben szereplő gyűrűaxiómák közvetlen következménye, amelyet most le is ellenőrzünk. Rögtön alkalmazhatjuk az 5. pontban lévő …