|
| |
|
|
Solving diophantine equations by factorization in number fields
Hrnčiar, Maroš ; Kala, Vítězslav (advisor) ; Příhoda, Pavel (referee)
Title: Solving diophantine equations by factorization in number fields Author: Bc. Maroš Hrnčiar Department: Department of Algebra Supervisor: Mgr. Vítězslav Kala, Ph.D., Mathematical Institute, University of Göttingen Abstract: The question of solvability of diophantine equations is one of the oldest mathematical problems in the history of mankind. While different approaches have been developed for solving certain types of equations, this thesis predo- minantly deals with the method of factorization over algebraic number fields. The idea behind this method is to express the equation in the form L = yn where L equals a product of typically linear factors with coefficients in a particular number field. Provided that several assumptions are met, it follows that each of the factors must be the n-th power of an element of the field. The structure of number fields plays a key role in the application of this method, hence a crucial part of the thesis presents an overview of algebraic number theory. In addition to the general theoretical part, the thesis contains all the necessary computations in specific quadratic and cubic number fields describing their basic characteristics. However, the main objective of this thesis is solving specific examples of equati- ons. For instance, in the case of equation x2 + y2 = z3 we...
|
|
| |
|
| |
|
| |
|
| |
|
|
Smart's algorithm
Sladovník, Tomáš ; Příhoda, Pavel (advisor) ; Šťovíček, Jan (referee)
The discrete logarithm problem is one of the most common trap- door functions in asymmetric cryptography and the use of elliptic curves over a finite field with prime characteristics seems to be a very efficient platform. This paper addresses the solution of a special type of elliptic curves where the number of points is equal to the characteristic of a field. Our goal is to construct a linear algorithm in goup operations and prove correctness. In order to create the algorithm, we will implement p-adic numbers, introduce the theory of formal groups and the formal logarithm and subgroups of an elliptic curve over the field of p-adic numbers. We will show that this type of curves is absolutely useless for cryptography because these curves are not safe. 1
|
|
|
Advanced techniques for calculations of discrete logarithm
Matocha, Vojtěch ; Příhoda, Pavel (advisor) ; Jedlička, Přemysl (referee)
Let G be a finite cyclic group. Solving the equation g^x = y for a given generator g and y is called the discrete logarithm problem. This problem is at the core of many modern cryptographic transformations. In this paper we provide a survey of algorithms to attack this problem, including the function field sieve, the fastest known algorithm applicable to the multiplicative group of a finite field. We also discuss the index calculus algorithm and some techniques improving its performance: the Coppersmith's algorithm and the polynomial sieving. The most important contribution of this paper is a C-language implementation of the function field sieve and its application to real inputs.
|
|
| |
|
|
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
|
guest ::
