Скачать или смотреть Diszkrét matematika 210410b Számelmélet és Algoritmusok

Az előadás főbb témái és időpontjai:

Maradékos osztás és kongruencia: Az előadó feleleveníti az alapfokú maradékos osztást, majd bevezeti a számelméleti kongruencia fogalmát és az ekvivalencia-relációkat [03:55].

Euklideszi algoritmus: Részletesen ismerteti a legnagyobb közös osztó (LNKO) meghatározására szolgáló algoritmust [08:19], bemutatva annak lépéseit és gyorsaságát. Említésre kerül Lamé tétele is, amely az algoritmus lépésszámát korlátozza [18:52].

Diofantikus egyenletek: A lineáris diofantikus egyenletek megoldhatóságának feltételeit és a kiterjesztett euklideszi algoritmust tárgyalja [22:07]. Bemutatja, hogyan kereshető meg az összes megoldás egy konkrét gyökből kiindulva [49:28].

Moduláris aritmetika: Szó esik a maradékosztályokról (Zn), a műveletekről és a multiplikatív inverz kiszámításáról [01:03:32].

Euler-féle fi-függvény: Ismerteti a függvény definícióját, kiszámítási módját prímtényezős felbontás alapján, valamint az Euler-Fermat tételt [01:13:09].

Gyorshatványozás (Ismételt négyzetre emelés): Bemutatja, hogyan lehet nagy kitevőjű hatványok maradékát hatékonyan kiszámolni, ami kulcsfontosságú a modern titkosításban [01:24:03].

Kínai maradéktétel (CRT): Kongruencia-egyenletrendszerek megoldását tárgyalja, különös tekintettel a páronként relatív prím modulusokra [01:39:25].

RSA algoritmus: Az előadás végén a nyilvános kulcsú titkosítás alapjait, a kódolás és dekódolás folyamatát, valamint a digitális aláírás elvét magyarázza el [01:52:15].