Diszkrét matematika 210410b Számelmélet és Algoritmusok скачать в хорошем качестве

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].