Episode I: Alice és Bob
. rész: Az RSA algoritmus helyes működése – bizonyítás
Posted on

Mivel teljesül az kongruencia, ezért a 3. pontja alapján teljesül az alábbi oszthatóság: Az oszthatóság ja alapján ekkor létezik olyan egész szám, amelyre teljesül az alábbi egyenlet: Mindkét oldalhoz -et adva: Azt kell tehát bizonyítani, …

Episode I: Alice és Bob
. rész: RSA-dekódolás gyorsítása – bizonyítás
Posted on

A kongruencia a 3. pontja alapján az alábbi oszthatóság teljesülését jelenti: Ez az oszthatóság a alapján azt jelenti, hogy létezik olyan egész szám, amelyre teljesül az alábbi egyenlet: Az egyenlet mindkét oldalához -t adva az …

Episode I: Alice és Bob
. rész: Maradékosztálygyűrűk dekompozíciója – bizonyítás
Posted on

Az függvényről a ben igazoltuk, hogy minden -beli rendezett párhoz pontosan egy -beli maradékosztályt rendel hozzá. Méghozzá azt a maradékosztályt, amely a rendezett pár két komponensének a metszete. A ben pedig azt mutattuk meg, hogy …

Episode I: Alice és Bob
. rész: Gyűrűk direkt szorzata, szorzatgyűrű – bizonyítás
Posted on

A ban felsorolt gyűrűaxiómákat kell ellenőrizni: A művelet kommutativitása könnyedén adódik az , , …, gyűrűkön értelmezett összeadások ugyanezen tulajdonságából: Hasonlóképpen adódik a művelet asszociativitása: És a művelet asszociativitása is: Továbbá a két művelet közötti …

Episode I: Alice és Bob
. rész: A kínai maradéktétel megfordítása – bizonyítás
Posted on

A tétel bizonyításához az alábbi két állítást kell igazolni: Az maradékosztály valóban az maradékosztálypár metszete, azaz . Nincs másik olyan maradékosztálypár a halmazban, amelynek a metszete lenne. Az 1. állítás: A utáni megjegyzés 5. pontja …

Episode I: Alice és Bob
. rész: A kínai maradéktétel alternatív megfogalmazása – bizonyítás
Posted on

Az és maradékosztályok metszete pontosan azokat az egész számokat fogja tartalmazni, amelyek mindkét maradékosztályban benne vannak. Ezek az alábbi kongruenciarendszert kielégítő egész számok lesznek: A kínai maradéktétel () alapján ezek az egész számok pontosan egy …

Episode I: Alice és Bob
. rész: Kínai maradéktétel – bizonyítás
Posted on

Először a kongruenciarendszer megoldhatóságát igazoljuk. Az első kongruencia a alapján pontosan akkor oldható meg, ha az kitüntetett közös osztónak többszöröse a jobboldalon álló egész szám. Ehhez hasonlóan a második kongruencia pontosan akkor oldható meg, ha …

Episode I: Alice és Bob
. rész: A kis Fermat-tétel – bizonyítás
Posted on

Amennyiben relatív prím a modulushoz, akkor alkalmazható az Euler-Fermat tétel (). Eszerint teljesül az alábbi kongruencia: A alapján az Euler-féle -függvény értéke ebben az esetben . Ebből a tétel első állítása adódik: Ám ebben az …

Episode I: Alice és Bob
. rész: Az RSA algoritmus helyes működése
Posted on

Tegyük fel, hogy teljesülnek az alábbi feltételek: Legyen adott két tetszőleges, egymástól különböző pozitív prímszám: és . Képezzük ezekből az modulust. Képezzük az Euler-féle -függvény értékét az modulusra, azaz kiszámítjuk a egész számot (erre vonatkozóan …

Episode I: Alice és Bob
. rész: RSA-dekódolás gyorsítása
Posted on

Legyen egy tetszőleges pozitív egész szám, pedig egy tetszőleges pozitív prímszám. Tegyük fel továbbá, hogy egy olyan egész szám, amelyre teljesül az alábbi kongruencia: Ekkor minden egész szám esetén teljesül az alábbi kongruencia is:

Episode I: Alice és Bob
. rész: Maradékosztálygyűrűk dekompozíciója
Posted on

Legyenek és valamilyen pozitív egész számok, továbbá tegyük fel, hogy és egymáshoz relatív prímek. Ekkor a szerint értelmezett gyűrű izomorf a maradékosztálygyűrűvel (lásd a t). Azaz: Legyenek , és tetszőleges egész számok, továbbá tegyük fel, …

Episode I: Alice és Bob
. rész: A kínai maradéktétel megfordítása
Posted on

Legyenek és valamilyen pozitív egész számok, továbbá tegyük fel, hogy és egymáshoz relatív prímek. Ekkor minden maradékosztályhoz pontosan egy olyan maradékosztálypár létezik, amelynek a metszete, azaz amelyre teljesül az alábbi: Amennyiben az maradékosztályt egy valamilyen …

Episode I: Alice és Bob
. rész: A kínai maradéktétel alternatív megfogalmazása
Posted on

Legyenek és valamilyen pozitív egész számok, továbbá tegyük fel, hogy és egymáshoz relatív prímek. Ekkor minden rendezett pár esetén . Tegyük fel, hogy az és egész számok kielégítik az alábbi kongruenciákat: Amennyiben az és maradékosztályokat …

Episode I: Alice és Bob
. rész: Gyűrűk direkt szorzata, szorzatgyűrű
Posted on

Legyenek , , …, tetszőleges gyűrűk, és értelmezzünk két műveletet az halmaz tetszőleges és elemei között az alábbi módon: Azaz a illetve a műveleteket úgy kell elvégezni, hogy az azonos pozícióban lévő komponensek összegeit illetve …

Episode I: Alice és Bob
. rész: Kínai maradéktétel
Posted on

Legyen és tetszőleges, és pedig valamilyen pozitív egész számok. Tegyük fel továbbá, hogy és egymáshoz relatív prímek. Ekkor az alábbi kongruenciarendszer megoldható, és a megoldás egyetlen modulo maradékosztály lesz: Más megfogalmazásban minden, a fenti két …

Episode I: Alice és Bob
. rész: A kis Fermat-tétel
Posted on

Legyen egy tetszőleges pozitív prím, továbbá egy tetszőleges egész szám, amely relatív prím -hez. Ekkor teljesül az alábbi kongruencia: Az alábbi kongruencia tetszőleges egész számra – tehát nem csak a -hez relatív prímekre – teljesül:

Episode I: Alice és Bob
. rész: Halmazok direkt szorzata
Posted on

Legyenek és tetszőleges halmazok. Ekkor az és halmazok direkt szorzatának (vagy Descartes-szorzatának) nevezzük azt a halmazt, amely az összes olyan rendezett párt tartalmazza, amelynek első komponense valamilyen -beli, második komponense pedig valamilyen -beli elem. Ezt …

Episode I: Alice és Bob
21. rész: Alice és Bob titkosít
Posted on

Hogyan működik az Internet biztonságát adó RSA nevű aszimmetrikus kulcsú rejtjelező eljárás? Hogyan kell előállítani a publikus és titkos kulcsokat? Hogyan lehet az euklidészi algoritmust lineáris kongruenciák megoldásához is használni? Hogyan kell kiszámítani az Euler-függvény értékét egy adott számra, és milyen információra van ehhez szükség?

Episode I: Alice és Bob
. rész: Lineáris diofantoszi egyenlet összes megoldása – megjegyzés
Posted on

A tételben szereplő 2. és 3. állítást egyben is megfogalmazhatjuk az alábbi módon: Ha az lineáris diofantoszi egyenlet valamelyik , megoldását már ismerjük, akkor az alábbi képlet segítségével megkaphatjuk az összes megoldást, amennyiben a paraméterrel …