Let p be a prime, p a power of p and 𝔽q the finite field with q elements. Any function φ: 𝔽q → 𝔽q can be unqiuely represented by a polynomial, 𝔽φ of degree < q. If the map x ↦ Fφ(x) induces a permutation on the underlying field we say Fφ is a permutation polynomial. Permutation polynomials have applications in many diverse fields of mathematics. In this dissertation we are generally concerned with the following question: Given a polynomial f, when does the map x ↦ F(x) induce a permutation on 𝔽q. In the second chapter we are concerned the permutation behavior of the polynomial gn,q, a q-ary version of the reversed Dickson polynomial, when the integer n is of the form n = qa - qb - 1. This leads to the third chapter where we consider binomials and trinomials taking special forms. In this case we are able to give explicit conditions that guarantee the given binomial or trinomial is a permutation polynomial. In the fourth chapter we are concerned with permutation polynomials of 𝔽q, where q is even, that can be represented as the sum of a power function and a linearized polynomial. These types of permutation polynomials have applications in cryptography. Lastly, chapter five is concerned with a conjecture on monomial graphs that can be formulated in terms of polynomials over finite fields.

This thesis introduces a new tower field representation, optimal tower fields (OTFs), that facilitates efficient finite field operations. The recursive direct inversion method presented for OTFs has significantly lower complexity than the known best method for inversion in optimal extension fields (OEFs), i.e., Itoh-Tsujii's inversion technique. The complexity of OTF inversion algorithm is shown to be O(m^2), significantly better than that of the Itoh-Tsujii algorithm, i.e. O(m^2(log_2 m)). This complexity is further improved to O(m^(log_2 3)) by utilizing the Karatsuba-Ofman algorithm. In addition, it is shown that OTFs are in fact a special class of OEFs and OTF elements may be converted to OEF representation via a simple permutation of the coefficients. Hence, OTF operations may be utilized to achieve the OEF arithmetic operations whenever a corresponding OTF representation exists. While the original OTF multiplication and squaring operations require slightly more additions than their OEF counterparts, due to the free conversion, both OTF operations may be achieved with the complexity of OEF operations. Furthermore, efficient finite field algorithms are introduced which significantly improve OTF multiplication and squaring operations. The OTF inversion algorithm was implemented on the ARM family of processors for a medium and a large sized field whose elements can be represented with 192 and 320 bits, respectively. In the implementation, the new OTF inversion algorithm ran at least six to eight times faster than the known best method for inversion in OEFs, i.e., Itoh-Tsujii inversion technique. According to the implementation results obtained, it is indicated that using the OTF inversion method an elliptic curve scalar point multiplication operation can be performed at least two to three times faster than the known best implementation for the selected fields.

Submitted by Geandra Rodrigues (geandrar@gmail.com) on 2018-10-30T13:59:20Z No. of bitstreams: 1 ednailtonsantossilva.pdf: 606910 bytes, checksum: 393b9af5bb01a2b06e9ebb6ee0eee4cb (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-11-23T12:29:01Z (GMT) No. of bitstreams: 1 ednailtonsantossilva.pdf: 606910 bytes, checksum: 393b9af5bb01a2b06e9ebb6ee0eee4cb (MD5) / Made available in DSpace on 2018-11-23T12:29:01Z (GMT). No. of bitstreams: 1 ednailtonsantossilva.pdf: 606910 bytes, checksum: 393b9af5bb01a2b06e9ebb6ee0eee4cb (MD5) Previous issue date: 2018-09-13 / O objetivo desse trabalho é apresentar algumas classes clássicas e outras mais recentes de polinômios de permutação sobre corpos finitos. A fim de atingir esse objetivo, apresentamos a construção e uma lista de propriedades de corpos finitos, bem como uma introdução à teoria dos polinômios sobre corpos finitos. / The main goal of this text is to present some known classes of permutation polynomials over finite fields. With this goal, we begin by presenting the construction and some properties of finite fields, as well as an introduction to the theory of polynomials over finite fields.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-01-13T13:41:39Z No. of bitstreams: 1 marianadealmeidanerycoutinho.pdf: 1084614 bytes, checksum: dded13e49c590fa1685ce4a2b9e5cf3c (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-01-25T17:33:13Z (GMT) No. of bitstreams: 1 marianadealmeidanerycoutinho.pdf: 1084614 bytes, checksum: dded13e49c590fa1685ce4a2b9e5cf3c (MD5) / Made available in DSpace on 2016-01-25T17:33:13Z (GMT). No. of bitstreams: 1 marianadealmeidanerycoutinho.pdf: 1084614 bytes, checksum: dded13e49c590fa1685ce4a2b9e5cf3c (MD5) Previous issue date: 2015-03-10 / FAPEMIG - Fundação de Amparo à Pesquisa do Estado de Minas Gerais / O estudo das curvas algébricas sobre corpos finitos, o qual está intrinsecamente relacionado à teoria dos corpos de funções sobre corpos finitos, é de grande interesse na álgebra abstrata, com destaque para aplicações na teoria dos números e na teoria dos códigos. Com essa motivação, estamos aqui interessados em estudar a existência de corpos de funções F/Fq com um número prescrito de lugares de determinados graus, estando baseados em algumas seções do artigo de ANBAR e STICHTENOTH (2013). Para isso, faremos também uma abordagem acerca da teoria geral dos corpos de funções, apresentando os principais elementos que nos auxiliarão na compreensão dos resultados anteriormente mencionados. / The study of algebraic curves over finite fields, which is intrinsically related to the theory of function fields over finite fields, is of great interest in abstract algebra, especially for applications in number theory and coding theory. With this motivation, we are here interested in studying the existence of function fields with a prescribed number of places of certain degrees, based on some sections of the paper of ANBAR and STICHTENOTH (2013). For this, we will also make a study of the general theory of function fields, showing the main elements that will assist us in understanding the results mentioned above.

Thesis (MSc)--Stellenbosch University, 2013. / ENGLISH ABSTRACT: See the full text for the abstract / AFRIKAANSE OPSOMMING: Sien volteks vir die opsomming

Computing discrete logarithms is a long-standing algorithmic problem, whose hardness forms the basis for numerous current public-key cryptosystems. In the case of finite fields of small characteristic, however, there has been tremendous progress recently, by which the complexity of the discrete logarithm problem (DLP) is considerably reduced. This habilitation thesis on the DLP in such fields deals with two principal aspects. On one hand, we develop and investigate novel efficient algorithms for computing discrete logarithms, where the complexity analysis relies on heuristic assumptions. In particular, we show that logarithms of factor base elements can be computed in polynomial time, and we discuss practical impacts of the new methods on the security of pairing-based cryptosystems. While a heuristic running time analysis of algorithms is common practice for concrete security estimations, this approach is insufficient from a mathematical perspective. Therefore, on the other hand, we focus on provable complexity results, for which we modify the algorithms so that any heuristics are avoided and a rigorous analysis becomes possible. We prove that for any prime field there exist infinitely many extension fields in which the DLP can be solved in quasi-polynomial time. Despite the two aspects looking rather independent from each other, it turns out, as illustrated in this thesis, that progress regarding practical algorithms and record computations can lead to advances on the theoretical running time analysis -- and the other way around. / Die Berechnung von diskreten Logarithmen ist ein eingehend untersuchtes algorithmisches Problem, dessen Schwierigkeit zahlreiche Anwendungen in der heutigen Public-Key-Kryptographie besitzt. Für endliche Körper kleiner Charakteristik sind jedoch kürzlich erhebliche Fortschritte erzielt worden, welche die Komplexität des diskreten Logarithmusproblems (DLP) in diesem Szenario drastisch reduzieren. Diese Habilitationsschrift erörtert zwei grundsätzliche Aspekte beim DLP in Körpern kleiner Charakteristik. Es werden einerseits neuartige, erheblich effizientere Algorithmen zur Berechnung von diskreten Logarithmen entwickelt und untersucht, wobei die Laufzeitanalyse auf heuristischen Annahmen beruht. Unter anderem wird gezeigt, dass Logarithmen von Elementen der Faktorbasis in polynomieller Zeit berechnet werden können, und welche praktischen Auswirkungen die neuen Verfahren auf die Sicherheit paarungsbasierter Kryptosysteme haben. Während heuristische Laufzeitabschätzungen von Algorithmen für die konkrete Sicherheitsanalyse üblich sind, so erscheint diese Vorgehensweise aus mathematischer Sicht unzulänglich. Der Aspekt der beweisbaren Komplexität für DLP-Algorithmen konzentriert sich deshalb darauf, modifizierte Algorithmen zu entwickeln, die jegliche heuristische Annahme vermeiden und dessen Laufzeit rigoros gezeigt werden kann. Es wird bewiesen, dass für jeden Primkörper unendlich viele Erweiterungskörper existieren, für die das DLP in quasi-polynomieller Zeit gelöst werden kann. Obwohl die beiden Aspekte weitgehend unabhängig voneinander erscheinen mögen, so zeigt sich, wie in dieser Schrift illustriert wird, dass Fortschritte bei praktischen Algorithmen und Rekordberechnungen auch zu Fortentwicklungen bei theoretischen Laufzeitabschätzungen führen -- und umgekehrt.

In this dissertation the Bays-Lambossy theorem is generalized to GF(pn). The Bays-Lambossy theorem states that if two Cayley objects each based on GF(p) are isomorphic then they are isomorphic by a multiplier map. We use this characterization to show that under certain conditions two isomorphic Cayley objects over GF(pn) must be isomorphic by a function on GF(pn) of a particular type.

This thesis mainly concerns the cohomology of the moduli spaces ℳ3[2] and ℳ3,1[2] of genus 3 curves with level 2 structure without respectively with a marked point and some of their natural subspaces. A genus 3 curve which is not hyperelliptic can be realized as a plane quartic and the moduli spaces 𝒬[2] and 𝒬1[2] of plane quartics without respectively with a marked point are given special attention. The spaces considered come with a natural action of the symplectic group Sp(6,𝔽2) and their cohomology groups thus become Sp(6,𝔽2)-representations. All computations are therefore Sp(6,𝔽2)-equivariant. We also study the mixed Hodge structures of these cohomology groups. The computations for ℳ3[2] are mainly via point counts over finite fields while the computations for ℳ3,1[2] primarily uses a description due to Looijenga in terms of arrangements associated to root systems. This leads us to the computation of the cohomology of complements of toric arrangements associated to root systems. These varieties come with an action of the corresponding Weyl group and the computations are equivariant with respect to this action.

This work presents several results on curves of Hurwitz type, defined over a finite field. In 1961, Tallini investigated plane irreducible curves of minimum degree containing all points of the projective plane PG(2,q) over a finite field of order q. We prove that such curves are Fq3(q2+q+1)-projectively equivalent to the Hurwitz curve of degree q+2, and compute some of itsWeierstrass points. In addition, we prove that when q is prime the curve is ordinary, that is, the p-rank equals the genus of the curve. We also compute the automorphism group of such curve and show that some of the quotient curves, arising from some special cyclic automorphism groups, are still curves of Hurwitz type. Furthermore, we solve the problem of explicitly describing the set of all Weierstrass pure gaps supported by two or three special points on Hurwitz curves. Finally, we use the latter characterization to construct Goppa codes with good parameters, some of which are current records in the Mint table. / Este trabalho apresenta vários resultados em curvas do tipo Hurwitz, definidas sobre um corpo finito. Em 1961, Tallini investigou curvas planas irredutíveis de grau mínimo contendo todos os pontos do plano projetivo PG(2,q) sobre um corpo finito de ordem q. Provamos que tais curvas são Fq3(q2+q+1)-projetivamente equivalentes à curva de Hurwitz de grau q+2, e calculamos alguns de seus pontos de Weierstrass. Em adição, provamos que, quando q é primo, a curva é ordinária, isto é, o p-rank é igual ao gênero da curva. Também calculamos o grupo de automorfismos desta curva e mostramos que algumas das curvas quocientes, construídas a partir de certos grupos cíclicos de automorfismos, são ainda curvas do tipo Hurwitz. Além disso, solucionamos o problema de descrever explicitamente o conjunto de todos os gaps puros de Weierstrass suportados por dois ou três pontos especiais em curvas de Hurwitz. Finalmente, usamos tal caracterização para construir códigos de Goppa com bons parâmetros, sendo alguns deles recordes na tabela Mint.

Este trabalho é essencialmente sobre pontos racionais em curvas algébricas sobre corpos finitos ou, equivalentemente, lugares racionais em corpos de funções algébricas em uma variável sobre corpos finitos. O objetivo é a demonstração da existência de constantes aq e bq &isin; R&gt; 0 tais que se g &ge; aq. N + bq, então existe uma curva sobre Fq de gênero g com N pontos racionais. / This work is essentially about rational points on algebraic curves over finite fields or, equivalently, rational places on algebraic function fields of one variable over finite fields. The aim is the proof of the existence of constants aq and bq &isin; R&gt; 0 such that if g &ge; aq &isin; aq . N+bq then there exists a curve over Fq of genus g with N rational points.