Neste trabalho, consideramos o problema de calcular o reticulado de subcorpos de uma extensão separável e de grau nito k( )/k. Isto e, queremos encontrar todos os corpos L tais que k L k( ). Até recentemente, o algoritmo utilizado pela maioria dos Sistemas Algébricos Computacionais baseava-se em um problema combinatorial nas raízes do polinômio minimal f de sobre k. Em 2013, um algoritmo foi apresentado para encontrar tais subcorpos. Este método calcula um pequeno conjunto de subcorpos, chamados de subcorpos principais, com a propriedade de que todo subcorpo de k( )/k e a interseção de alguns destes subcorpos. Assim, calcular o reticulado de subcorpos e dividido em duas etapas: 1) Encontrar os subcorpos principais de k( )/k e 2) Calcular todas as interseções destes subcorpos. A primeira etapa pode ser feita em tempo polinomial. Entretanto, a segunda etapa não pode e assim, domina a complexidade do algoritmo. Nosso objetivo e melhorar a segunda etapa, tanto em teoria quanto na prática. Para isso, mostramos como rapidamente calcular todas as interseções entre os subcorpos principais. Embora a complexidade continue não sendo limitada polinomialmente (e também não poderia ser, pois o número total de subcorpos não o é), conseguimos melhorar a complexidade do algoritmo. Também notamos um melhoramento na prática, principalmente quando o número de subcorpos e grande. Além disso, estudamos dois casos especiais: corpos numéricos e o corpo das funções racionais. Para corpos numéricos (i.e., quando k = Q), também apresentamos um melhoramento para a primeira etapa. No segundo caso, os subcorpos da extensão k(t)=k(f(t)), definida por f(t) 2 k(t), nos fornecem decomposições da função racional f(t). Nosso algoritmo tem uma performance melhor que algoritmos anteriores para calcular as decomposições de funções racionais. / In this work, we consider the problem of computing the sub eld lattice of a separable and nite degree eld extension k( )/k. That is, we wish to nd all elds L such that k L k( ). Until recently, the algorithm used by most Computer Algebraic Systems relied on a combinatorial problem on the roots of the minimal polynomial f of over k, which can be a computationally expensive task. In 2013, another algorithm was presented to nd the sub eld lattice of k( )/k. This method computes a small set of sub elds, called principal sub elds, with the property that any other sub eld of k( )/k is the intersection of some of these principal sub elds. Thus, the problem of computing the sub eld lattice can be split into 2 steps: 1) Find the principal sub elds of k( )/k and 2) Compute all intersections of these sub elds. The rst step can be executed in polynomial time however, the second step can not and thus, dominates the algorithm complexity.Our main goal is to improve the second step, both theoretically and practically. More speci cally, we develop a method to quickly compute all intersections of principal sub elds. While the complexity is still not polynomially bounded (in fact, it can not be for the total number of sub elds is not polynomially bounded), this new method helps to improve the non-polynomial part of the complexity. Practical performance is also improved when the number of intersections is large. We also focus on two special cases: number elds and rational function elds. For the number eld case (i.e., when k = Q), we also present an improvement for the rst step. For the rational function eld case, computing the sub eld lattice of the extension K(t)=K(f(t)) de ned by f(t) 2 K(t) yields all decompositions of the rational function f(t). Our algorithm outperforms previous algorithms for computing rational function decompositions.

Neste trabalho, consideramos o problema de calcular o reticulado de subcorpos de uma extensão separável e de grau nito k( )/k. Isto e, queremos encontrar todos os corpos L tais que k L k( ). Até recentemente, o algoritmo utilizado pela maioria dos Sistemas Algébricos Computacionais baseava-se em um problema combinatorial nas raízes do polinômio minimal f de sobre k. Em 2013, um algoritmo foi apresentado para encontrar tais subcorpos. Este método calcula um pequeno conjunto de subcorpos, chamados de subcorpos principais, com a propriedade de que todo subcorpo de k( )/k e a interseção de alguns destes subcorpos. Assim, calcular o reticulado de subcorpos e dividido em duas etapas: 1) Encontrar os subcorpos principais de k( )/k e 2) Calcular todas as interseções destes subcorpos. A primeira etapa pode ser feita em tempo polinomial. Entretanto, a segunda etapa não pode e assim, domina a complexidade do algoritmo. Nosso objetivo e melhorar a segunda etapa, tanto em teoria quanto na prática. Para isso, mostramos como rapidamente calcular todas as interseções entre os subcorpos principais. Embora a complexidade continue não sendo limitada polinomialmente (e também não poderia ser, pois o número total de subcorpos não o é), conseguimos melhorar a complexidade do algoritmo. Também notamos um melhoramento na prática, principalmente quando o número de subcorpos e grande. Além disso, estudamos dois casos especiais: corpos numéricos e o corpo das funções racionais. Para corpos numéricos (i.e., quando k = Q), também apresentamos um melhoramento para a primeira etapa. No segundo caso, os subcorpos da extensão k(t)=k(f(t)), definida por f(t) 2 k(t), nos fornecem decomposições da função racional f(t). Nosso algoritmo tem uma performance melhor que algoritmos anteriores para calcular as decomposições de funções racionais. / In this work, we consider the problem of computing the sub eld lattice of a separable and nite degree eld extension k( )/k. That is, we wish to nd all elds L such that k L k( ). Until recently, the algorithm used by most Computer Algebraic Systems relied on a combinatorial problem on the roots of the minimal polynomial f of over k, which can be a computationally expensive task. In 2013, another algorithm was presented to nd the sub eld lattice of k( )/k. This method computes a small set of sub elds, called principal sub elds, with the property that any other sub eld of k( )/k is the intersection of some of these principal sub elds. Thus, the problem of computing the sub eld lattice can be split into 2 steps: 1) Find the principal sub elds of k( )/k and 2) Compute all intersections of these sub elds. The rst step can be executed in polynomial time however, the second step can not and thus, dominates the algorithm complexity.Our main goal is to improve the second step, both theoretically and practically. More speci cally, we develop a method to quickly compute all intersections of principal sub elds. While the complexity is still not polynomially bounded (in fact, it can not be for the total number of sub elds is not polynomially bounded), this new method helps to improve the non-polynomial part of the complexity. Practical performance is also improved when the number of intersections is large. We also focus on two special cases: number elds and rational function elds. For the number eld case (i.e., when k = Q), we also present an improvement for the rst step. For the rational function eld case, computing the sub eld lattice of the extension K(t)=K(f(t)) de ned by f(t) 2 K(t) yields all decompositions of the rational function f(t). Our algorithm outperforms previous algorithms for computing rational function decompositions.

Neste trabalho, consideramos o problema de calcular o reticulado de subcorpos de uma extensão separável e de grau nito k( )/k. Isto e, queremos encontrar todos os corpos L tais que k L k( ). Até recentemente, o algoritmo utilizado pela maioria dos Sistemas Algébricos Computacionais baseava-se em um problema combinatorial nas raízes do polinômio minimal f de sobre k. Em 2013, um algoritmo foi apresentado para encontrar tais subcorpos. Este método calcula um pequeno conjunto de subcorpos, chamados de subcorpos principais, com a propriedade de que todo subcorpo de k( )/k e a interseção de alguns destes subcorpos. Assim, calcular o reticulado de subcorpos e dividido em duas etapas: 1) Encontrar os subcorpos principais de k( )/k e 2) Calcular todas as interseções destes subcorpos. A primeira etapa pode ser feita em tempo polinomial. Entretanto, a segunda etapa não pode e assim, domina a complexidade do algoritmo. Nosso objetivo e melhorar a segunda etapa, tanto em teoria quanto na prática. Para isso, mostramos como rapidamente calcular todas as interseções entre os subcorpos principais. Embora a complexidade continue não sendo limitada polinomialmente (e também não poderia ser, pois o número total de subcorpos não o é), conseguimos melhorar a complexidade do algoritmo. Também notamos um melhoramento na prática, principalmente quando o número de subcorpos e grande. Além disso, estudamos dois casos especiais: corpos numéricos e o corpo das funções racionais. Para corpos numéricos (i.e., quando k = Q), também apresentamos um melhoramento para a primeira etapa. No segundo caso, os subcorpos da extensão k(t)=k(f(t)), definida por f(t) 2 k(t), nos fornecem decomposições da função racional f(t). Nosso algoritmo tem uma performance melhor que algoritmos anteriores para calcular as decomposições de funções racionais. / In this work, we consider the problem of computing the sub eld lattice of a separable and nite degree eld extension k( )/k. That is, we wish to nd all elds L such that k L k( ). Until recently, the algorithm used by most Computer Algebraic Systems relied on a combinatorial problem on the roots of the minimal polynomial f of over k, which can be a computationally expensive task. In 2013, another algorithm was presented to nd the sub eld lattice of k( )/k. This method computes a small set of sub elds, called principal sub elds, with the property that any other sub eld of k( )/k is the intersection of some of these principal sub elds. Thus, the problem of computing the sub eld lattice can be split into 2 steps: 1) Find the principal sub elds of k( )/k and 2) Compute all intersections of these sub elds. The rst step can be executed in polynomial time however, the second step can not and thus, dominates the algorithm complexity.Our main goal is to improve the second step, both theoretically and practically. More speci cally, we develop a method to quickly compute all intersections of principal sub elds. While the complexity is still not polynomially bounded (in fact, it can not be for the total number of sub elds is not polynomially bounded), this new method helps to improve the non-polynomial part of the complexity. Practical performance is also improved when the number of intersections is large. We also focus on two special cases: number elds and rational function elds. For the number eld case (i.e., when k = Q), we also present an improvement for the rst step. For the rational function eld case, computing the sub eld lattice of the extension K(t)=K(f(t)) de ned by f(t) 2 K(t) yields all decompositions of the rational function f(t). Our algorithm outperforms previous algorithms for computing rational function decompositions.

Submitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2018-03-14T17:24:36Z No. of bitstreams: 2 Dissertação - Angie Tatiana Suárez Romero - 2018.pdf: 2209912 bytes, checksum: 0ad7489cc1457ed892d896b3aa2f4885 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-03-15T11:07:28Z (GMT) No. of bitstreams: 2 Dissertação - Angie Tatiana Suárez Romero - 2018.pdf: 2209912 bytes, checksum: 0ad7489cc1457ed892d896b3aa2f4885 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-03-15T11:07:28Z (GMT). No. of bitstreams: 2 Dissertação - Angie Tatiana Suárez Romero - 2018.pdf: 2209912 bytes, checksum: 0ad7489cc1457ed892d896b3aa2f4885 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-03-05 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / Cayley’s theorem allows us to represent a finite group as a permutations group of a finite set of points. In general, an action of a finite group G in a finite set, is described as an application of the group G in the symmetric group Sym(Ω). In this work we will describe some algorithms for permutation groups and implement them in the GAP system. We begin by describing a way of representing groups in computers, we calculate orbits, stabilizers in the basic form and by means of Schreier’s vectors. Later we make algorithms to work with primitive and transitive groups, thus arriving at the concept of BSGS, base and strong generator set, for permutation groups with the algorithm SCHREIERSIMS. In the end we work with group homomorphisms, we find the elements of a group through backtrack searches. / O Teorema de Cayley nos permite representar um grupo finito como grupo de permutações de um conjunto finito de pontos. De forma geral, uma ação de um grupo finito G em um conjunto finito Ω, é descrita como uma aplicação do grupo G no grupo simétrico Sym(Ω). Neste trabalho vamos descrever alguns algoritmos para grupos de permutação e implementa-los no sistema GAP. Começamos descrevendo uma maneira de representar grupos em computadores, calculamos órbitas, estabilizadores na forma básica e por meio de vetores de Schreier. Posteriormente fazemos algoritmos para trabalhar com grupos transitivos e primitivos, chegando assim ao conceito de, base e conjunto gerador forte (BSGS) para grupos de permutação finitos com o algoritmo SCHREIER-SIMS. No final trabalhamos com homomorfismos de grupos e encontramos os elementos de um grupo mediante pesquisas backtrack.

A presente dissertação aborda uma técnica para determinar as soluções de sistemas de equações polinomiais. Esta técnica que é puramente algébrica, interliga tópicos da Matemática, como a Geometria Algébrica e a Álgebra Computacional. Mais especificamente, estudamos a teoria de Resultantes e suas aplicações. Começamos com a motivação de encontrar as raízes comuns de dois polinômios a uma variável, em seguida é estendida para o caso mais geral de várias variáveis. Estudamos detalhadamente como obter fórmulas para o cálculo do Resultante, como por exemplo a fórmula de Macaulay e de Poisson. A técnica para resolver sistemas de equações polinomiais é então apresentada. Terminamos apresentando uma prova de um caso particular do Teorema de Bezout, como aplicação da teoria de Resultantes. Este teorema é muito importante, pois fornece um número de soluções de um sistema de equações polinomiais.

Nesta dissertação apresentamos os principais algoritmos para o cálculo do Máximo Divisor Comum de polinômios a uma variável: os Algoritmos Euclidianos e os Algoritmos Modulares. Obtemos uma nova cota superior para os coeficientes do M.D.C., bem como demonstramos os resultados necessários para a obtenção da cota atualmente utilizada pelos Algoritmos Modulares. Além disso, apresentamos uma classe de polinômios para os quais a nova cota é menor que a anterior. / In this thesis we present the main algorithms for computing the Greatest Common Divisor of two univariate polynomials: the Euclidean Algorithms and the Modular Algorithms. We obtain a new upper bound for the coefficients of the G.C.D., as well we prove the results that are necessary for obtaining the bound that has been used by the Modular Algorithms. Besides, we present a class of polynomials for which the new bound is smaller than the previos one.

A presente dissertação aborda uma técnica para determinar as soluções de sistemas de equações polinomiais. Esta técnica que é puramente algébrica, interliga tópicos da Matemática, como a Geometria Algébrica e a Álgebra Computacional. Mais especificamente, estudamos a teoria de Resultantes e suas aplicações. Começamos com a motivação de encontrar as raízes comuns de dois polinômios a uma variável, em seguida é estendida para o caso mais geral de várias variáveis. Estudamos detalhadamente como obter fórmulas para o cálculo do Resultante, como por exemplo a fórmula de Macaulay e de Poisson. A técnica para resolver sistemas de equações polinomiais é então apresentada. Terminamos apresentando uma prova de um caso particular do Teorema de Bezout, como aplicação da teoria de Resultantes. Este teorema é muito importante, pois fornece um número de soluções de um sistema de equações polinomiais.

Nesta dissertação apresentamos os principais algoritmos para o cálculo do Máximo Divisor Comum de polinômios a uma variável: os Algoritmos Euclidianos e os Algoritmos Modulares. Obtemos uma nova cota superior para os coeficientes do M.D.C., bem como demonstramos os resultados necessários para a obtenção da cota atualmente utilizada pelos Algoritmos Modulares. Além disso, apresentamos uma classe de polinômios para os quais a nova cota é menor que a anterior. / In this thesis we present the main algorithms for computing the Greatest Common Divisor of two univariate polynomials: the Euclidean Algorithms and the Modular Algorithms. We obtain a new upper bound for the coefficients of the G.C.D., as well we prove the results that are necessary for obtaining the bound that has been used by the Modular Algorithms. Besides, we present a class of polynomials for which the new bound is smaller than the previos one.

A presente dissertação aborda uma técnica para determinar as soluções de sistemas de equações polinomiais. Esta técnica que é puramente algébrica, interliga tópicos da Matemática, como a Geometria Algébrica e a Álgebra Computacional. Mais especificamente, estudamos a teoria de Resultantes e suas aplicações. Começamos com a motivação de encontrar as raízes comuns de dois polinômios a uma variável, em seguida é estendida para o caso mais geral de várias variáveis. Estudamos detalhadamente como obter fórmulas para o cálculo do Resultante, como por exemplo a fórmula de Macaulay e de Poisson. A técnica para resolver sistemas de equações polinomiais é então apresentada. Terminamos apresentando uma prova de um caso particular do Teorema de Bezout, como aplicação da teoria de Resultantes. Este teorema é muito importante, pois fornece um número de soluções de um sistema de equações polinomiais.

Nesta dissertação apresentamos os principais algoritmos para o cálculo do Máximo Divisor Comum de polinômios a uma variável: os Algoritmos Euclidianos e os Algoritmos Modulares. Obtemos uma nova cota superior para os coeficientes do M.D.C., bem como demonstramos os resultados necessários para a obtenção da cota atualmente utilizada pelos Algoritmos Modulares. Além disso, apresentamos uma classe de polinômios para os quais a nova cota é menor que a anterior. / In this thesis we present the main algorithms for computing the Greatest Common Divisor of two univariate polynomials: the Euclidean Algorithms and the Modular Algorithms. We obtain a new upper bound for the coefficients of the G.C.D., as well we prove the results that are necessary for obtaining the bound that has been used by the Modular Algorithms. Besides, we present a class of polynomials for which the new bound is smaller than the previos one.