Title: Applications of Gröbner bases in cryptography Author: Aleš Fuchs Department: Department of Algebra Supervisor: Mgr. Jan Št'ovíček Ph.D., Department of Algebra Abstract: In the present paper we study admissible orders and techniques of multivariate polynomial division in the setting of polynomial rings over finite fields. The Gröbner bases of some ideal play a key role here, as they allow to solve the ideal membership problem thanks to their properties. We also explore features of so called reduced Gröbner bases, which are unique for a particular ideal and in some way also minimal. Further we will discuss the main facts about Gröbner bases also in the setting of free algebras over finite fields, where the variables are non-commuting. Contrary to the first case, Gröbner bases can be infinite here, even for some finitely generated two- sided ideals. In the last chapter we introduce an asymmetric cryptosystem Polly Cracker, based on the ideal membership problem in both commutative and noncommutative theory. We analyze some known cryptanalytic methods applied to these systems and in several cases also precautions dealing with them. Finally we summarize these precautions and introduce a blueprint of Polly Cracker reliable construction. Keywords: noncommutative Gröbner bases, Polly Cracker, security,...

Estudaremos a teoria de bases de Gröbner em anéis de polinômios comutativos com coeficientes em uma nelnoetheriano e em anéis de operadores diferencias. Apresentaremos, em ambos casos, uma generalização do algoritmo da divisão, do S-polinômio e do algoritmo de Buchberger para calcular bases de Gröbner. / We study the theory of Gröbner bases for commutative polynomials rings over a noetherian ring and of rings of differential operators. In both cases we exhibit a generalization of the division algorithm, the S -polynomial and the Buchberger algorithm for computing Gröbner bases.

Estudaremos a teoria de bases de Gröbner em anéis de polinômios comutativos com coeficientes em uma nelnoetheriano e em anéis de operadores diferencias. Apresentaremos, em ambos casos, uma generalização do algoritmo da divisão, do S-polinômio e do algoritmo de Buchberger para calcular bases de Gröbner. / We study the theory of Gröbner bases for commutative polynomials rings over a noetherian ring and of rings of differential operators. In both cases we exhibit a generalization of the division algorithm, the S -polynomial and the Buchberger algorithm for computing Gröbner bases.

In this thesis, we address problems from two topics of applied mathematics: linear integer programming and polyhedral computation. Linear integer programming concerns solving optimisation problems to maximise a linear cost function over the set of integer points in a polyhedron. Polyhedral computation is concerned with algorithms for computing different properties of convex polyhedra. First, we explore the theory and computation of Gröbner bases and Markov bases for linear integer programming. Second, we investigate and improve an algorithm from polyhedral computation that converts between different representations of cones and polyhedra. A Markov basis is a set of integer vectors such that we can move between any two feasible solutions of an integer program by adding or subtracting vectors in the Markov basis while never moving outside the set of feasible solutions. Markov bases are mainly used in algebraic statistics for sampling from a set of feasible solutions. The major contribution of this thesis is a fast algorithm for computing Markov bases, which we used to solve a previously intractable computational challenge. Gröbner basis methods are exact local search approaches for solving integer programs. We present a Gröbner basis approach that can use the structure of an integer program in order to solve it more efficiently. Gröbner basis methods are interesting mainly from a purely theoretical viewpoint, but they are also interesting because they may provide insight into why some classes of integer programs are difficult to solve using standard techniques and because someday they may be able to solve these difficult problems. Computing the properties of convex polyhedra is useful for solving problems within different areas of mathematics such as linear programming, integer programming, combinatorial optimisation, and computational geometry. We investigate and improve an algorithm for converting between a generator representation of a cone or polyhedron and a constraint representation of the cone or polyhedron and vice versa. This algorithm can be extended to compute circuits of matrices, which are used in computational biology for metabolic pathway analysis.

Orientador: Fernando Eduardo Torres Orihuela / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-11T03:53:44Z (GMT). No. of bitstreams: 1 Tizziotti_GuilhermeChaud_D.pdf: 891044 bytes, checksum: 4e90b377185548b051c39ead60bdf183 (MD5) Previous issue date: 2008 / Resumo: Estendemos resultados de Heegard, Little e Saints relacionados a bases de Gröbner para códigos Hermitianos pontuais. Trabalhamos com códigos Hermitianos bipontuais e n-pontuais, e com códigos sobre a curva Norma-Traço. Além disso, determinamos o semigrupo de Weierstrass de um certo par de pontos racionais sobre a curva Norma-Traço e com esse semigrupo conseguimos melhorar a cota da distância mínima de códigos construídos sobre tais curvas / Abstract: We extend results of Heegard, Little and Saints concerning the Gröbner basis algorithm for one-point Hermitian codes. We work with two-point and n-point Hermitian codes and codes arising from the Norm-Trace curve. We also determine the Weierstrass semigroup at a certain pair of rational points in such curves and uses these computations to improve the lower bound on the minimum distance of two-point algebraic geometry codes arising from them / Doutorado / Algebra, Geometria Algebrica / Doutor em Matemática

Les nombres p-adiques sont un analogue des nombres réels plus proche de l’arithmétique. L’avènement ces dernières décennies de la géométrie arithmétique a engendré la création de nombreux algorithmes utilisant ces nombres. Ces derniers ne peuvent être de manière générale manipulés qu’à précision finie. Nous proposons une méthode, dite de précision différentielle, pour étudier ces problèmes de précision. Elle permet de se ramener à un problème au premier ordre. Nous nous intéressons aussi à la question de savoir quelles bases de Gröbner peuvent être calculées sur les p-adiques. / P-Adic numbers are a field in arithmetic analoguous to the real numbers. The advent during the last few decades of arithmetic geometry has yielded many algorithms using those numbers. Such numbers can only by handled with finite precision. We design a method, that we call differential precision, to study the behaviour of the precision in a p-adic context. It reduces the study to a first-order problem. We also study the question of which Gröbner bases can be computed over a p-adic number field.

The topics explored in this project present and interesting picture of close connections between algebra and geometry. Given a specific system of polynomial equations we show how to construct a Groebner basis using Buchbergers Algorithm. Gröbner bases have very nice properties, e.g. they do give a unique remainder in the division algorithm. We use these bases to solve systems of polynomial quations in several variables and to determine whether a function lies in the ideal.

Since Buchberger intrduced the theory of Gröbner bases in 1965 it has become one of the most important tools in constructive algebra and, nowadays, it is the kernel of many algorithms in the theory of polynomial ideals and algebraic geometry. Motivated by the results in polynomial rings there have been investigeated al lot of possibilities to generalise Buchberger's ideas to other types of rings. The perhaps most general concept, though it does not cover all extensions reported in the literature, is the extension to graded structures due to Robbiano and Mora. But in order to obtain algorithmic solutions for the compution of Gröbner bases it needs additional computability assumptions. The subject of this paper is the presentation of some classes of effective graded structures.

We report on some experience with a new version of the well known Gröbner algorithm with factorization and constraint inequalities, implemented in our REDUCE package CALI, [12]. We discuss some of its details and present run time comparisons with other existing implementations on well splitting examples.

A cosmological polytope of an undirected connected graph is a lattice polytope which when the graph is interpreted as a feynman diagram can be used to calculate the contribution of that feynman diagram to the wavefunction of some cosmological models. This contribution can be calculated using the canonical form of the cosmological polytope, which can be computed by taking the sum of the canonical forms of the facets of a subdivision of the cosmological polytope. Juhnke-Kubitzke, Solus and Venturello showed that the cosmological polytope of any undirected connected graph has a regular unimodular triangulation. They characterized the facets of such triangulations for trees and cycles to yield combinatorial formula for the desired canonical forms. Here we characterize the facets of such a triangulation of the cosmological polytope of the complete bipartite graph K_{2,n} and use that characterization to calculate the normalized volume. / Ett kosmologiskt polytop av en oriktad sammanhängande graf är ett gitterpolytop, vilket när grafen tolkas som ett feynman diagram kan användas för att beräkna bidraget av feynman diagrammet till vågfunktionen av vissa kosmologiska modeller. Detta bidrag can beräknas genom att använda den kanoniska formen av det kosmologiska polytopet, som kan beräknas genom att ta summan av de kanoniska formerna av facetterna av en uppdelning av det kosmologiska polytopet. Juhnke-Kubitzke, Solus och Venturello visade att det kosmologiska polytopet av en oriktad sammanhängande graf har en reguljär unimodulär triangulering. De karaktäriserar facetterna av sådana trianguleringar av träd och cykliska grafer, vilket ger en kombinatorisk formel för de kanoniska formerna av intresse. Här karaktäriserar vi facetterna av en sådan trianguleraing för det kosmologiska polytopet av den kompletta bipartita grafen K_{2,n} och använder denna karaktärisering för att beräkna den normaliserade volymen.