The first half of this thesis is devoted to the study of finite polynomial maps en --4 en and the use of Grobner bases to determine if a given map is finite. We begin by examining those maps which have quasihomogeneous components, and give a simple condition for such maps to be finite. This condition is extended to those maps which are quasihomogeneous as above, but with extra lower order terms. Next, we give a general criterion for testing the finiteness of a given polynomial map and an implementation in the Maple computer algebra system. Our next step is to generalize our results to regular maps between affine varieties. Again, a finiteness criterion is given, plus its implementation in Maple. Lastly in this half, we consider the trace bilinear form associated with a finite map and show how it may be used to find real roots of a polynomial system. The second half of the thesis is concerned with the study of G-variant map germs, which commute with the action of a finite group G on the source and target spaces. We give a relation between the G-variant degree associated with a map germ, bilinear forms on the local algebra and preimages of zero under a perturbation of the original map. We look at both the complex and real affine space situation. We then give the equivalent results when we do not have a 'good' deformation of the map, when we have two groups acting and when we use modular representations. Next, we give an invariant of G-variant maps which is stronger than G-degree, based upon a lattice of vector subspaces. Finally, we examine the structure of the class of G-variant maps and consider criteria for maps to have 'good' deformations and to be finite. We then give ways of determining generators for the class of maps by generalizing theorems of Noether and Molien.

Let K be a field and Q a finite directed multi-graph. In this paper I classify all path algebras KQ and admissible orders with the property that all of their finitely generated ideals have finite Groebner bases. / Master of Science

Groebner bases have many applications in mathematics, science, and engineering. This dissertation deals with the algorithmic aspects of computing these bases. The dissertation begins with a brief introduction of fundamental concepts about Groebner bases. Following this a discussion of various implementation issues are discussed. Much of the practical difficulties of using Groebner basis algorithms and techniques stems from the high computational complexity. It is shown that the algorithmic complexity of computing a Groebner basis primarily stems from the calculation of normal forms. This is established by studying run profiles of various computations. This leads to two options of making Groebner basis techniques more practical. They are to reduce the complexity by developing new algorithms (heuristics) or reduce running time of normal form calculations by introducing concurrency. The later approach is taken in the remainder of the dissertation where a multithreaded normal form algorithm is presented and discussed. It is shown with a simple example that the new algorithm demonstrates a speedup and scalability. The algorithm also has the advantage of being completion strategy independent. We conclude with an outline of future research involving the new algorithm.

No description available.

We develop a public key cryptosystem whose security is based on the intractability of the ideal membership problem for a noncommutative algebra over a finite field. We show that this system, which is the noncommutative analogue of the Polly Cracker cryptosystem, is more secure than the commutative version. This is due to the fact that there are a number of ideals of noncommutative algebras (over finite fields) that have infinite reduced Groebner bases, and can be used to generate a public key. We present classes of such ideals and prove that they do not have a finite Groebner basis under any admissible order. We also examine various techniques to realize finite Groebner bases, in order to determine whether these ideals can be used effectively in the design of a public key cryptosystem. We then show how some of these classes of ideals, which have infinite reduced Groebner bases, can be used to design a public key cryptosystem. We also study various techniques of encryption. Finally, we study techniques of cryptanalysis that may be used to attack the cryptosystems that we present. We show how poorly constructed public keys can in fact, reveal the private key, and discuss techniques to design public keys that adequately conceal the private key. We also show how linear algebra can be used in ciphertext attacks and present a technique to overcome such attacks. This is different from the commutative version of the Polly Cracker cryptosystem, which is believed to be susceptible to "intelligent" linear algebra attacks. / Ph. D.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this work, we present a special class of linear codes: parameterized affine codes. We show that these codes are easy to construct and that given a parameterized affine code one can easily obtain an equivalent projective parameterized code equivalent to it. We also studied some topics which served as the theoretical foundations for the work, such as the theory of Groebner Bases, the footprint of an ideal and some topics of algebraic geometry and commutative algebra. This work has as main goal to obtain the basic parameters (length, dimension and minimum distance) of parameterized codes related and also to relate them to the projective parameterized codes, as done in [7]. We finish by applying the theory of Groebner Bases to the footprint of a certain ideal in order to obtain the basic parameters of the parameterized code over an affine torus. / Neste trabalho apresentamos uma classe especial de códigos lineares: os códigos parametrizados afins. Mostramos que esses códigos são de fácil construção e que, dado um código parametrizado afim, pode-se facilmente obter um código parametrizado projetivo equivalente a ele. Também estudamos algumas teorias que nos serviram como base teórica tais como: a teoria de Bases de Groebner e a Pegada de um ideal e alguns tópicos de geometria algébrica e álgebra comutativa. Este trabalho tem por objetivo principal obter os parâmetros básicos (comprimento, dimensão e distância mínima) dos códigos parametrizados afins e relacioná-los com os códigos parametrizados projetivos, assim como na referência [7]. Encerramos aplicando a teoria de Bases de Groebner a Pegada de um ideal para obter os parâmetros básicos do código parametrizado no toro afim. / Mestre em Matemática

Le problème d’´équivalence de code joue un rôle important dans la théorie de code et la cryptographie basée sur le code. Cela est dû à son importance dans la classification des codes ainsi que dans la construction et la cryptanalyse des cryptosystèmes à base de codes. Il est également lié à un problème ouvert d’isomorphisme de graphes, un problème bien connu dans le domaine de la théorie de la complexité. Nous prouvons pour les codes ayant un hull trivial qu’il existe une réduction polynomiale de l’équivalence par permutation de codes à l’isomorphisme de graphes. Cela montre que cette sous-classe d’équivalence de permutation n’est pas plus dure que l’isomorphisme de graphes. Nous introduisons une nouvelle méthode pour résoudre le problème d’équivalence de code. Nous développons des approches algébriques pour résoudre le problème dans ses deux versions : en permutation et en diagonale. Nous construisons un système algébrique en établissant des relations entre les matrices génératrices et les matrices de parité des codes équivalents. Nous nous retrouvons avecun système plusieurs variables d’équations linéaires et quadratiques qui peut être résolu en utilisant des outils algébriques tels que les bases de Groebner et les techniques associées. Il est possible en théorie de résoudre l’équivalence de code avec des techniques utilisant des bases de Groebner. Cependant, le calcul en pratique devient complexe à mesure que la longueur du code augmente. Nous avons introduit plusieurs améliorations telles que la linéarisation par bloc et l’action de Frobenius. En utilisant ces techniques, nous identifions de nombreux cas où le problème d’équivalence de permutation peut être résolu efficacement. Notre méthode d’équivalence diagonale résout efficacement le problème dans les corps de petites tailles, à savoir F3 et F4. L’augmentation de la taille du corps entraîne une augmentation du nombre de variables dans notre système algébrique, ce qui le rend difficile à résoudre. Nous nous intéressons enfin au problème d’isomorphisme de graphes en considérant un système algébrique quadratique pour l’isomorphisme de graphes. Pour des instances tirées aléatoirement, le système possède des propriétés intéressantes en termes de rang de la partie linéaire et du nombre de variables. Nousrésolvons efficacement le problème d’isomorphisme de graphes pour des graphes aléatoires avec un grand nombre de sommets, et également pour certains graphes réguliers tels que ceux de Petersen, Cubical et Wagner.123 / Code equivalence problem plays an important role in coding theory and code based cryptography.That is due to its significance in classification of codes and also construction and cryptanalysis of code based cryptosystems. It is also related to the long standing problem of graph isomorphism, a well-known problem in the world of complexity theory. We introduce new method for solving code equivalence problem. We develop algebraic approaches to solve the problem in its permutation and diagonal versions. We build algebraic system by establishing relations between generator matrices and parity check matrices of the equivalent codes. We end up with system of multivariables of linear and quadratic equations which can be solved using algebraic tools such as Groebner basis and related techniques. By using Groebner basis techniques we can solve the code equivalence but the computation becomes complex as the length of the code increases. We introduced several improvements such as block linearization and Frobenius action. Using these techniques we identify many cases where permutation equivalence problem can be solved efficiently. Our method for diagonal equivalence solves the problem efficiently in small fields, namely F3 and F4. The increase in the field size results in an increase in the number of variables in our algebraic system which makes it difficult to solve. We introduce a new reduction from permutation code equivalence when the hull is trivial to graph isomorphism. This shows that this subclass of permutation equivalence is not harder than graph isomorphism.Using this reduction we obtain an algebraic system for graph isomorphism with interesting properties in terms of the rank of the linear part and the number of variables. We solve the graph isomorphism problem efficiently for random graphs with large number of vertices and also for some regular graphs such as Petersen, Cubical and Wagner Graphs.