| |
|
Generating polynomials for number field sieve
Pejlová, Anežka ; Drápal, Aleš (advisor) ; Příhoda, Pavel (referee)
Title: Generating polynomials for number field sieve Author: Anežka Pejlová Department: Department of Algebra Supervisor: prof. RNDr. Aleš Drápal, CSc., DSc., Department of Algebra Abstract: The topic of this thesis is mainly focused on Kleinjung algorithm for generating polynomials within the General Number Field Sieve, which is the most efficient factorization algorithm nowadays. Commonly used consecu- tions are explained with respect to the fact whether they can be rigorously proven or they are based only on heuristic assumptions. Another contribution of this thesis is the attached implementation of Kleinjung algorithm develo- ped as a part of the Number Field Sieve project led by the Department of Algebra. The appropriateness of some heuristics used in the theory beyond the Kleinjung algorithm is supported by empirical data obtained from this implementation. Keywords: Number field sieve, Kleinjung algorithm
|
|
Modular and p-adic codes
Sobotka, Miloslav ; Šťovíček, Jan (advisor) ; Příhoda, Pavel (referee)
Název práce: Modulární a p-adické kódy Autor: Bc. Miloslav Sobotka Katedra: Katedra algebry Vedoucí diplomové práce: RNDr. Jan Šťovíček, Ph.D., Katedra algebry, MFF UK Abstrakt: Cílem práce bylo studium modulárních kódů nad okruhy Zpe a kódů p-adických. Motivací byla představa posloupnosti kódů nad do sebe vnořenými okruhy Zpe , kdy kódy nad menšími okruhy mají tu vlastnost, že je lze získat z kódu nad vyšším okruhem operací modulo. Naopak při budování této posloup- nosti volíme zdvihy tak, aby tato podmínka zůstala zachována. Tento koncept vede k celé řadě otázek týkajících se kvality zdvižených, či řekněme snížených kó- dů, od zachování parametrů kódů, přes samodualitu a cykličnost až po studium chování váhového výčtu. Klíčová slova: modulární kód, p-adický kód, teorie invariantů, váhový výčet, MacWilliamsové identita Title: Modular and p-adic codes Author: Bc. Miloslav Sobotka Department: Department of Algebra Supervisor: RNDr. Jan Šťovíček, Ph.D., Department of Algebra, MFF UK Abstract: The aim of this thesis was to study modular codes over rings Zpe and p-adic codes. The motivation was the idea of a sequence of codes over nested rings Zpe , where the codes over smaller rings are obtained from the codes over larger rings using the modulo operation. Conversely, when constructing such a sequence we choose...
|
|
Number Field Sieve for Discrete Logarithm
Godušová, Anna ; Jedlička, Přemysl (advisor) ; Příhoda, Pavel (referee)
Many of today's cryptographic systems are based on the discrete logarithm problem, e.g. the Diffie-Hellman protocol. The number field sieve algorithm (NFS) is the algorithm solving the problem of factorization of integers, but latest works show, it can be also applied to the discrete logarithm problem. In this work, we study the number field sieve algorithm for discrete logarithm and we also compare the NFS for discrete logarithm with the NFS for factoriza- tion. Even though these NFS algorithms are based on the same principle, many differences are found. 1
|
| |
|
Lineární kódy nad okruhy
Kobrle, Tomáš ; Šťovíček, Jan (advisor) ; Příhoda, Pavel (referee)
This master thesis focus on special type of rings called path algebras with a goal to define and describe codes over these rings. The path algebras are defined by graphic structures called quivers which is transferred also on the modules of the path algebra. Codes themselves are defined over indecomposible injective modules of path algebra considering the latest result in ring-coding theory. So defined codes allow us to study the parameters and the versions of elementary theorems from theory of linear codes over fields for codes over rings. These are about duals codes especially, the MacWilliams identity theorem and about code equivalency. Finally we get back to path algebras and describe a way to make them applicable in theory of codes over rings.
|
|
Complexity of some factoring algorithms
Štěpánek, Vilém ; Příhoda, Pavel (advisor) ; Jedlička, Přemysl (referee)
Thesis is devoted to estimate complexity of algorithms running time for factorization of integer using ECM. Firstly, basic characteristic of elliptic curves over finite fields are sketched and presented two theorems on which this problematic is based. Consequently, there are given necessary estimates by some constants and ECM algorithms behavior is sketched. After that there is shown estimated complexity of algorithm ECM and finally there is specified implementation of factoring algorithm ECM.
|
|
Ideal lattices in cryptography
Vyhnalová, Sára ; Kala, Vítězslav (advisor) ; Příhoda, Pavel (referee)
The thesis is focused on the theory of special lattices that are important in cryptography, namely ideal, cyclic and NTRU lattices. Specifically, we expand and generalise the work of Ding and Lindner on Identifying Ideal Lattices. The algorithm for identifying ideal lattices is included, along with illustrative examples and more detailed proofs of propositions on which the algorithm is based. In the section about Lattice Isomorphism there is also included a generalised theorem from the paper. We extend the result of identifying the NTRU lattices and supplement it with several examples. The thesis also contains Chapter Applications in Cryptography where we describe a cryptographic hash function based on ideal lattices. And finally, we provide a brief overview of the cryptographic algorithms using NTRU lattices.
|
|
The theorem about 27 lines
Till, Daniel ; Šťovíček, Jan (advisor) ; Příhoda, Pavel (referee)
In this work we will prove there are exactly 27 different lines on each non- singular cubic surface over an agebraically closed field not of characteristic two. Firstly, we will focus on affine algebraic varieties and their ideals. We will prove Hilbert's Nullstellensatz and introduce morphisms between affine algebraic va- rieties. Then we move on to projective algebraic varieties and their ideals. We introduce morphisms between projective varieties and nomenclature for selected types of projective varieties. We will prove auxiliary statements about intersection of two distinct lines in a projective plane, respectively a line and a plane in P3 K. We also define concepts such as a tangent space to variety at a given point, sin- gularity of a hypersurface and irreducible variety. Then we move to P3 K, where we will prove the existence of 27 different lines on any nonsingular cubic surface. We will firstly prove that there is a line on such a surface and then we construct all 27 lines by mutual relations. 1
|
|
Distinguished elements of group rings
Procházková, Zuzana ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
Title: Distinguished elements of group rings Author: Bc. Zuzana Procházková Department: Department of Algebra Supervisor: doc. Mgr. et Mgr. Jan Žemlička, Ph.D., Department of Algebra Abstract: This thesis is about finding idempotents in a group ring. We describe three techniques of finding idempotents in a semisimple group ring and in the last chapter there is an attempt to find idempotents in a group ring that does not have to be semisimple. The first technique uses representations and characters of a group. The second technique finds idempotents through the use of Shoda pairs. The third technique lifts idempotent from the factor ring with the help of CNC system of ideals, which is a generalization of a well-known technique with nilpotent ideals, and it is here extended to group rings formed by non-abelian group and noncommutative ring. iii
|