|
|
Frobeniovy testy prvočíselnosti
Hora, Jan ; Drápal, Aleš (vedoucí práce) ; Holub, Štěpán (oponent)
Název práce: Frobeniovy testy prvočíselnosti Autor: Jan Hora Katedra (ústav): katedra algebry Vedoucí diplomové práce: prof. RNDr. Aleš Drápal, CSc. Dsc. e-mail vedoucího: drapal@karlin.mff.cuni.cz Abstrakt: V následující práci se zabýváme rozšířeným kvadratickým Frobeniovým testem prvočíselnosti. Studujeme důvody jeho funkčnosti, a jeho úspěšnost a výpočetní složitost. Zkonstruujeme okruh R(n, c), ve kterém test probíhá, a popíšeme jeho strukturu v závislosti na tom, zda testované číslo n je či není složené. Popíšeme algoritmus Frobeniova testu, a ukážeme, že test vždy uspěje, je-li n prvočíslem. Dále zjistíme, jaká je zaručená úspěšnost testu. Ukážeme, že test selže právě při výběru jistých prvků z množiny R(n, c), jejich množinu označíme G(n, c). Najdeme podmínky, které musí G(n, c) splňovat, a díky nim zjistíme, že pravděpodobnost selhání Frobeniova testu je nejvýše 1 24 . Poté rozborem složitosti jednotlivých částí algoritmu zjistíme, že k provedení jednoho cyklu Frobeniova testu stačí přibližně 2 log n násobení v Zn. Nakonec porovnáme teoretické odhady s prakticky získanými výsledky. Klíčová slova: test prvočíselnosti, Frobeniův automorfismus, cyklická grupa, odmocniny z jedné 1
|
|
|
Rozšířený binární Golayův kód
Uchytilová, Vendula ; Drápal, Aleš (vedoucí práce) ; Hora, Jan (oponent)
Tato práce pojednává o třech konstrukcích rozšířeného binárního Golayova kódu G24. První konstrukce vychází z projektivní roviny řádu čtyři. Z ní je vybudován Steinerův systém (5, 8, 24). Lineární obal jeho bloků tvoří lineární binární [24, 12, 8] kód C. Každý binární [24, 12, 8] kód je izomorfní kódu C, který se nazývá rozšířený binární Gola- yův kód G24. Druhá konstrukce využívá takzvaný Miracle Octad Generator (MOG). Všechna MOG-slova váhy osm tvoří také Steinerův systém (5, 8, 24). Třetí konstrukce využívá nestrannou kombinatorickou hru Mogul. Pomocí jejích P-pozic lze vytvořit li- neární binární [24, 12, 8] kód. Určení jeho parametrů usnadní skutečnost, že se jedná o lexikografický kód. 1
|
|
|
MDS codes conjecture
Kesely, Michal ; Drápal, Aleš (vedoucí práce) ; Lisoněk, Petr (oponent)
V předloženej práci skúmame niektoré vlastnosti MDS kódov a venujeme sa najma domnienke o MDS kódoch. Najprv MDS kódy predstavíme, uvedieme ich príklady a základné vlastnosti, napríklad ich súvislosť s latinskými štvorcami alebo odlžnikmi. Neskor pristúpime k MDS domnienke a jej dokazovaniu v niektorých prípadoch. V tretej katipole uvedieme súvislosť medzi MDS kódmi a n-oblúkmi v propotívnych geometriách. Nakoniec ešte predstavíme preklad známych prípadov, pre ktoré je MDS domnienka dokázaná.
|
|
|
Algebraická teorie S-boxů
Ďuránová, Elena ; Tůma, Jiří (vedoucí práce) ; Drápal, Aleš (oponent)
Tato práce se zabývá popisem S-boxů z algebraického hlediska pomocí speciál- ního typu kvadratických rovnic, tzv. biafinních rovnic. Pro S-boxy vyšších řádů tyto biafinní rovnice nemusí existovat. Nicméně, pro speciální typ S-boxů je možné najít biaffinní rovnice, které je splňují i pro vyšší řády. Takovým typem je například S-box v blokové šifře Rijndael, složený z inverzní funkce a afinní transformace. Práce dokazuje, že počet biafinních rovnic splňujících S-box tohoto typu nezávisí na použití afinní transformace. Dále je dokázáno, že pro každý S-box řádu n, který je tvořen inverzní funkcí, existuje aspoň 3n − 1 biafinních rovnic, které jej splňují. 1
|
|
| |
|
| |
|
| |
|
| |
|
|
Applications of error-correcting codes in steganography
Cinkais, Roman ; Lisoněk, Petr (oponent) ; Drápal, Aleš (vedoucí práce)
Modern steganography is a relatively new discipline with many applications in information security. Contrary to the cryptography which is trying to make a message unreadable to third party using cryptographic algorithms, the aim of steganography is to hide a communication between parties. Applications of error-correcting codes and covering functions markedly increases abilities and security of steganographic algorithms. This thesis is attended to steganography using error-correcting codes which has the best results nowadays regarding embedding efficiency. New constructions will help us to work with non-linear codes and providing new steganographic algorithms. We will see that these algorithms have a better ability to hide communication, resp. a message in a digital medium. Further improvements can be made using applications of general q-ary codes. Many new questions are coming out with that which need to be answered. Several comparisons are showing that the area of steganography is in a beginning and we will be participants of such a progress as cryptography experienced in the last two decades.
|
|
|
Quasigroup based cryptography
Christov, Adam ; Drápal, Aleš (oponent) ; Stanovský, David (vedoucí práce)
Možnou alternativou k bežne používaným kryptografickým schématům s veřejným klíčem, jejichž složitost je založena na problému faktorizace nebo diskrétním logaritmu, jsou schémata využívající složitost rešení systému kvadratických rovnic o více proměnných nad konečným tělesem. Jedno takové schéma bylo navrhnuto v práci D.Gligoroskiho a spol. [8]. V tomto schématu jsou klíče konstruovány ze speciálních kvazigrup, které jsou nazývány kvadratické. V této práci jsou kvadratické kvazigrupy popsány a klasifikovány podle jejich vlastností. Nakonec je představena teorie, kterou je možné využít k jejich konstrukci.
|
host ::
RSS.