Elemi valószínűségszámítás, algoritmuselmélet

TTK Matematika BSc szak Adattudomány és Operációkutatás sávjánk kötelezően választható tárgya

Létezés és véletlen. Véletlent használó egzisztanciabizonyítások nevezetes példákon keresztül, ezek algoritmikus vonatkozásai. Derandomizálás. Néhány nevezetes randomizált algoritmus elemzése. A gyorsrendezés várható lépésszáma. 

A Rabin–Miller-prí­mteszt elemzése. A Schwartz–Zippel-lemma és közvetlen alkalmazásai. Randomizált mintaillesztés. Minimális feszítőfa számí­tása lineáris várható időben. Bolyongások és algoritmusok. Lovász lokális lemmája. A módszer ismertetése, néhány egyszerű alkalmazása, a módszer algoritmikus változata. Véletlen Erdős–Rényi-gráfok, néhány gráftulajdonság evolúciója. Barabási-gráfok, alkalmazásuk számítógépes, szociális, és biológiai hálózatok modellezésére.

Pszeudovéletlen sorozatok statisztikai és kriptográfiai tulajdonságai. Visszacsatolásos lépterű számlálók, véges testek, Galois-számlálók. A modern kriptográfiai alapelvek. Szimmetrikus és nyílt kulcsú titkosí­tások. Boole-függvények a kriptográfiában, S-dobozok, az AES rendszer. A korrelációs és az algebrai támadás. ElGamal és RSA rendszerek. Modulo n számolási feladatok bonyolultsága. A Pohlig–Hellman és az oldalcsatornás támadás az RSA ellen. Diszkrét logaritmus, Diffie–Hellman-kulcscsere. A kvantumtámadás, rejtett részcsoport probléma. A hibajavító kódolás alapfogalmai. Általánosított Reed–Solomon-kódok és dekódolásuk. A bináris dekódolás NP-teljessége. A McEliece-kriptorendszer. 

Kitekintés: Véletlen és bonyolultsági osztályok. Az RP és a Las Vegas nyelvosztályok, példákkal. Az IP nyelvosztály: nem izomorf gráfok, IP=PSPACE lényeges részének a bizonyátása. A BPP nyelvosztály, a BPP és a P viszonyával foglalkozó néhány eredmény vázlatos ismertetése. Az RL nyelvosztály. Nulla ismeretű bizonyítás fogalma, példák. Elliptikus görbék véges testek felett, elliptikus görbe kriptográfia. Rácsalapú és izogénia alapú posztkvantum kriptográfiai eljárások.

 

Existence and randomness. Existence proofs using randomness through notable examples and their algorithmic implications. Derandomization. Analysis of some notable randomized algorithms. Expected number of steps of a quick sorting.

Analysis of the Rabin–Miller primality test. The Schwartz–Zippel lemma and its direct applications. Randomized sample fitting. Computation of minimum spanning tree in linear expected time. Random walks and algorithms. Lovász' local lemma. Description of the method, some simple applications, and algorithmic version of the method. Random Erdő–Rényi graphs, the evolution of some graph properties. Barabási graphs, their application to computer, social and biological network modeling.

Statistical and cryptographic properties of random sequences. Feedback step counters, finite fields, Galois counters. Modern cryptographic principles. Symmetric and open key cryptography. Boolean functions in cryptography, S-boxes, and the AES system. Correlation and algebraic attack. ElGamal and RSA schemes. The complexity of modulo n computational problems. Pohlig–Hellman and side-channel attack against RSA. Discrete logarithm, Diffie–Hellman key exchange. The quantum attack, hidden subgroup problem. Basic concepts of error-correcting coding. Generalized Reed–Solomon codes and their decoding. NP-completeness of binary decoding. The McEliece cryptosystem. 

Insight: Random and complexity classes. RP and Las Vegas language classes, with examples. The IP language class: nonisomorphic graphs, proof of the essential part of IP=PSPACE. The language class BPP, the sketch of some results on the relation between BPP and P. The RL language class. The notion of zero-knowledge proof, examples. Elliptic curves over finite bodies, elliptic curve cryptography. Lattice-based and isogeny-based postquantum cryptography. 

A TVSZ szerint

Az oktatóval egyeztetve

Carlet, Claude (2021). Boolean Functions for Cryptography and Coding Theory. Cambridge: Cambridge University Press. doi:10.1017/9781108606806

Smart, Nigel P. (2017). Cryptography Made Simple. Series Information Security and Cryptography. Springer Cham. doi:10.1007/978-3-319-21936-3

Rónyai Lajos (2011). Véletlen és algoritmusok. Typotex Tankönyvtár online jegyzet. http://tankonyvtar.ttk.bme.hu/pdf/1.pdf

56

14

0

0

0

0

0

50

120

120

Dr. Nagy Gábor Péter

egyetemi tanár

BME, Algebra Tanszék

Dr. Rónyai Lajos

egyetemi tanár

Algebra Tanszék

Dr. Nagy Gábor Péter