This thesis explores the explicit computation of twists of curves. We develope an algorithm for computing the twists of a given curve assuming that its automorphism group is known. And in the particular case in which the curve is non-hyperelliptic we show how to compute equations of the twists. The algorithm is based on a correspondence that we establish beetwen the set of twists and the set of solutions of a certain Galois embedding problem. In general is not known how to compute all the solution of a Galois embedding problem. Throughout the thesis we give some ideas of how to solve these problems. The twists of curves of genus less or equal than 2 are well-known. While the genus 0 and 1 cases go back from long ago, the genus 2 case is due to the work of Cardona and Quer. All the genus 0, 1 or 2 curves are hyperelliptic, however for genus greater than 2 almost all the curves are non-hyperelliptic. As an application to our algorithm we give a classification with equations of the twists of all plane quartic curves, that is, the non-hyperelliptic genus 3 curves, defined over any number field k. The first step for computing such twists is providing a classification of the plane quartic curves defined over a concrete number field k. The starting point for doing this is Henn classification of plane quartic curves with non-trivial automorphism group over the complex numbers. An example of the importance of the study of the set of twists of a curve is that it has been proven to be really useful for a better understanding of the behaviour of the Generalize Sato-Tate conjecture, see the work of Fité, Kedlaya and Sutherland. We show a proof of the Sato-Tate conjecture for the twists of the Fermat and Klein quartics as a corollary of a deep result of Johansson, and we compute the Sato-Tate groups and Sato-Tate distributions of them. Following with the study of the Generalize Sato-Tate conjecture, in the last chapter of this thesis we explore such conjecture for the Fermat hypersurfaces X_{n}^{m}: x_{0}^{m}+...+x_{n+1}^{m} = 0. We explicitly show how to compute the Sato-Tate groups and the Sato-Tate distributions of these Fermat hypersurfaces. We also prove the conjecture over the rational numbers for n=1 and over than the cyclotomic field of mth-roots of the unity if n is greater 1. / En esta tesis estudiamos el cálculo explícito de twists de curvas. Se desarrolla un algoritmo para calcular los twists de una curva dada asumiendo que su grupo de automorfismos en conocido. Además, en el caso particular en que la curva es no hiperelíptica se enseña como calcular ecuaciones de los twists. El algoritmo está basado es una correspondencia que establecemos entre el conjunto de twists de la curva y el conjunto de soluciones a un cierto problema de embeding de Galois. Aunque no existe un método general para resolver este tipo de problemas a lo largo de la tesis se exponen algunas ideas para resolver algunos de estos problemas en concreto. Los twists de curvas de género menor o igual que 2 son bien conocidos. Mientras que los casos de género 0 y 1 se conocen desde hace tiempo, el caso de género 2 es más reciente y se debe al trabajo de Cardona y Quer. Todas las curvas de género, 0,1 y 2 son hiperelípticas, sin embargo, las curvas de género mayor o igual que 3 son en su mayoría no hipèrelípticas. Como aplicación a nuestro algoritmo damos una clasificación con ecuaciones de los twists de todas las cuárticas planas lisas, es decir, de todas las curvas no hiperelípticas de género 3, definidas sobre un cuerpo de números k. El primer paso para calcualr estos twists es obtener una clasificación de las cuárticas planas lisas definidas sobre un cuerpo de números k arbitrario. El punto de partida para obtener esta clasificación es la clasificación de Henn de cuárticas planas definidas sobre los números complejos y con grupo de automorfismos no trivial. Un ejemplo de la importancia del estudio de los twists de curvas es que se ha probado que resulta ser de gran utilidad para el mejor entendimiento del carácter de la conjetura de Sato-Tate generalizada, como puede verse en los trabajos de entre otros: Fité, Kedlaya y Sutherland. En la tesis se prueba la conjetura de Sato-Tate para el caso de los twists de las cuárticas de Fermat y de Klein como corolario de un resultado de Johansson, además se calculan los grupos y las distribuciones de Sato-Tate de estos twists. Siguiendo con el estudio de la conjetura generalizada de Sato-Tate, en el último capítulo de la tesis se estudia la conjetura para el caso de las hipersuperficies de Fermat: X_{n}^{m}: x_{0}^{m}+...+x_{n+1}^{m} = 0. Se muestra esplícitamente como calcular los grupos de Sato-Tate y las correspondientes distribuciones. Además se prueba la conjetura para el caso n=1 sobre el cuerpo de los números racionales y para n mayor que 1 sobre el cuerpo de las raíces m-ésimas de la unidad.

En aquest treball, considerem el problema de computar bases triangulars de clausures enteres d'anells locals unidimensionals. Es presenta "MaxMin", un algoritme eficient que empra representacions OM d'ideals primers per computar bases locals d'ideals fraccionaris de cossos de nombres i cossos de funcions. MaxMin garanteix que les bases generades són reduïdes i triangulars. D'aquesta manera, s'evita l'aplicació de rutines de triangularització, com ara el pas a la forma normal d'Hermite, que són lentes per a cossos de grau alt. Mostrem que aquest algoritme té la mateixa complexitat computacional asimptòtica que els mètodes ja existents basats en representacions OM. MaxMin ha estat desenvolupat i inclòs en el paquet +Ideals, dissenyat per treballar qüestions aritmètiques en cossos grans. La implementació quasi sempre és més ràpida que la de les altres rutines basades en representacions OM. Respecte a les rutines que es troben actualment als sistemes d'àlgebra computacional estàndard, la nostra implementació de MaxMin és també considerablement més ràpida, exceptuant casos concrets d'extensions de cossos molt petites. / En este trabajo, consideramos el problema de computar bases triangulares de clausuras enteras de anillos locales unidimensionales. Se presenta "MaxMin", un algoritmo eficiente que emplea representaciones OM de ideales primos para computar bases locales de ideales fraccionarios de cuerpos de números y cuerpos de funciones. MaxMin garantiza que las bases generadas son reducidas y triangulares. De este modo, se evita la aplicación de rutinas de triangularización, como el paso a la forma normal de Hermite, que son lentas para cuerpos de grado alto. Mostramos que este algoritmo tiene la misma complejidad computacional asintótica que los métodos ya existentes basados en representaciones OM. MaxMin ha sido desarrollado e incluido en +Ideals, un paquete diseñado para trabajar cuestiones aritméticas en cuerpos grandes. La implementación casi siempre es más rápida que las otras rutinas basadas en representaciones OM. Respecto a las rutinas que se encuentran actualmente en los sistemas de álgebra computacional estándard, nuestra implementación de MaxMin es de nuevo considerablemente más rápida, exceptuando casos concretos de extensiones de cuerpos muy pequeñas. / In this work, we consider the problem of computing triangular bases of integral closures of one-dimensional local rings. "MaxMin" is presented, an efficient algorithm which employs OM representations of prime ideals to compute local bases of fractional ideals of number fields and function fields. The proposed algorithm generates bases which are guaranteed to be reduced and triangular. In this way, it avoids the application of triangularisation routines, such as the Hermite Normal Form, which are slow for fields of large degree. We show that this algorithm has the same asymptotic computational complexity as existing methods based on OM representations. MaxMin has been developed and included as part of the +Ideals package for arithmetic in large fields. This implementation is almost always faster than existing OM-based routines. It is also considerably faster than the routines currently found in standard computer algebra systems, excepting some cases involving very small field extensions.

The background of this dissertation is the inverse Galois problem.Which finite groups can occur as Galois groups of an extension of the rational field? This problem was first considered by D. Hilbert, and it still remains open.Assume that a finite group G can be realized as a Galois group over Q. We can ask whether there exists some other finite Galois extension, with Galois group G and enjoying an additional ramification property. In this connection, several variants of the Inverse Galois Problem have been studied. In this dissertation, we shall address the following problem, posed by Brian Birch around 1994.Tame Inverse Galois Problem. Given a finite group G, is there a tamely ramified Galois extension K/Q with Galois group G?In this thesis we address this problem by studying the Galois representations attached to arithmetic-geometric objects such as elliptic curves, or more generally abelian varieties, and modular forms. We seek conditions that ensure that the action of the wild inertia group at all primes is trivial. Note that this strategy of constructing Galois representations such that the image of the wild inertia group at all primes is trivial can be encompassed in the general trend of constructing Galois representations with prefixed local behaviour.This dissertation is split into two parts. In the first part, we tackle the realization of families of two dimensional linear groups over a finite field as the Galois group of a tamely ramified extension of Q. We study the Galois representations attached to elliptic curves and to modular forms. In the second part we address the problem of realizing a family of four dimensional linear groups over a prime field as the Galois group of a tamely ramified extension of Q. In this part we study the action of the inertia group upon the l-torsion points of the formal group attached to an abelian variety, and obtain a general result that allows us to control the action of the wild inertia group. We apply this result to the formal group attached to abelian surfaces. More precisely, we consider the Jacobians of bielliptic supersingular genus 2 curves, suitably chosen so that we can control the size of the image of the corresponding representation.The main results we have obtained are the following.Theorem. Let l be a prime number. There exist infinitely many semistable elliptic curves E with good supersingular reduction at l. The Galois representation attached to the l-torsion points of E provides a tame Galois realization of GL(2, F_l).Furthermore, we give an explicit algorithm to construct these elliptic curves. The primes l=2, 3, 5, 7 have been considered separately.Theorem. Let l be a prime number greater than 3. There exist infinitely many genus 2 curves C such that the Galois representation attached to the l-torsion points of the Jacobian of C provides a tame Galois realization of GSp(4, F_l).As in the previous result, we give an explicit algorithm that enables us to construct these curves.In addition, we have obtained tame Galois realizations of groups of the form PSL(2, F_(l^2)) for several values of l. / Esta tesis se desarrolla en torno al Problema Inverso de la Teoría de Galois sobre el cuerpo de los números racionales. Este problema, que fue considerado por primera vez por D. Hilbert, es un problema abierto. En 1994, B. Birch plantea la siguiente variante de este problema, conocida como problema inverso moderado de la teoría de Galois. Dado un grupo finito G, ¿existe una extensión de Galois K/Q, moderadamente ramificada, con grupo de Galois G?En esta tesis abordamos este problema mediante el estudio de las representaciones de Galois asociadas a objetos aritmético-geométricos, concretamente a curvas elípticas, formas modulares y variedades abelianas. Encontramos condiciones explícitas que garantizan que para todo primo, la imagen del grupo de inercia salvaje es trivial.La memoria está dividida en dos partes. El objetivo de la primera parte es la obtención de realizaciones moderadas de grupos lineales 2-dimensionales sobre un cuerpo finito como grupos de Galois sobre Q. Dado un número primo l, demostramos que existen infinitas curvas elípticas semiestables E/Q con buena reducción supersingular en l. La representación de Galois asociada a los puntos de l-torsión de E da lugar a una realización de GL(2, F_l) como grupo de Galois de una extensión de Q moderadamente ramificada.A continuación se consideran las representaciones de Galois asociadas a formas modulares. Obtenemos realizaciones de Galois moderadas para algunos grupos de la familia PSL(2, F_(l^2)).El objetivo de la segunda parte es la obtención de realizaciones moderadas de los grupos lineales de la familia GSp(4, F_l).Estudiamos la acción de la inercia sobre los puntos de l-torsión del grupo formal asociado a una variedad abeliana, y obtenemos un resultado general que nos permite controlar la acción de la inercia salvaje. Aplicamos este resultado al caso de superficies abelianas. Concretamente, consideramos las Jacobianas de curvas de género 2 bielípticas supersingulares, construidas de forma conveniente para controlar la imagen de la representación asociada. Demostramos que, dado un número primo l mayor que 3, existen infinitas curvas C de género 2 tales que la representación de Galois asociada a los puntos de l-torsión de la Jacobiana de C proporciona una realización de GSp(4, F_l) como grupo de Galois de una extensión moderadamente ramificada de Q.

Aquesta tesi ha estat destacada amb la menció de PREMI EXTRAORDINARI DE DOCTORAT en l'àmbit de MATEMÀTIQUESCurs 1997 - 98 / A la present tesi ens hem ocupat fonamentalment de l'estudi matemàtic dels esquemes per a compartir secrets en les seves vessants de l'estudi de la taxa d'informació i de l'estudi dels esquemes segurs enfront l'acció de mentiders. Com a tema complementari hem estudiat la qüestió de l'arrel cúbica a l'anell dels enters mòdul m. Tots dos temes s'enquadren dins de la Criptologia.Pel que fa l'estudi dels esquemes per a compartir secrets, els nostres objectius han estat la caracterització de les estructures ideals i la fitació de la taxa d'informació òptima per a certes famílies d'estructures d'accés. La primera família estudiada ha estat la de les estructures definides per pesos i llindar. Hem trobat que totes es poden expressar mitjançant pesos i llindar naturals. Hem obtingut una caracterització completa de les de rang 2, és a dir, les que estan determinades per un graf que hem anomenat k-graf. Hem dissenyat un algorisme que les identifica a partir dels graus de cadascun dels vèrtexs i determina els pesos i llindar mínims. A partir de l'estructura d'aquests grafs hem determinat una fita inferior de la taxa d'informació òptima que és de l'ordre de 1/log n (amb n el número de participants), millorant la fita 1/2^{n/2} trobada amb l'únic esquema proposat fins ara per a aquestes estructures, degut a Shamir. A partir d'aquests resultats i mitjançant l'ús del dual d'una estructura hem extés els resultats anteriors a una nova família d'estructures. L'estudi general de les estructures definides per pesos i llindar de rang superior s'ha concentrat en trobar fites superiors i inferiors, especialment per les estructures definides per dos pesos. La segona família que hem estudiat és la de les estructures bipartites. Per les estructures bipartites, hem aconseguit caracteritzar totalment les que són ideals. Aquestes són la família d'estructures de quasi-llindar. Aquesta caracterització de les estructures ideals fa que les estructures de quasi-llindar juguin un paper dins de les estructures bipartites anàleg al paper que juguen els grafs multipartits complets dins de les estructures definides per grafs. Així és equivalent dir que una estructura bipartita és ideal a dir que és de quasi-llindar o a dir que és pot definir amb un esquema d'espai vectorial o a dir que la seva taxa d'informació òptima és més gran que 2/3. Per les estructures bipartites descrivim tècniques típiques de recobriment per tal de trobar fites inferiors de la taxa d'informació. Determinem un algorisme que permet trobar una fita superior de la taxa d'informació. Justifiquem que aquestes fites són ajustades.La següent família d'estructures que hem estudiat ha estat la de les estructures homogènies, obtenint resultats en la fitació inferior de la taxa d'informació. Hem proposat dues construccions d'esquemes per a compartir secrets per estructures homogènies basats en les tècniques de recobriments. Per avaluar les taxes d'informació hem definit el concepte de k-grau d'un participant en una estructura homogènia. Aquest paràmetre és la clau de tot l'estudi de les fites, de les comparacions entre elles i amb les conegudes fins ara. El resultat de la comparació indica que la segona d'elles ens dóna un esquema amb una taxa d'informació millor que la primera, però a canvi la primera utilitza un conjunt de secrets de mesura més realista. La comparació amb les proposades anteriorment mostra que les nostres són millors en la majoria dels casos. L'estudi de les fites superiors per les estructures homogènies l'hem encetat amb les de rang 3, trobant una primera fita superior per una subfamília d'estructures que és del mateix ordre que la fita inferior obtinguda per les nostres construccions. Pels esquemes segurs enfront l'acció de mentiders hem generalitzat els conceptes de seguretat per estructures de llindar al cas d'una estructura qualsevol, tant pel cas en el qual els mentiders no coneixen el secret, com pel cas que sí el coneixen. Hem trobat una fita superior de la taxa d'informació òptima per un esquema en el que una coalició de mentiders és detectada amb una certa probabilitat. Després d'aquest estudi general, hem proposat un esquema per a compartir secrets per a una estructura d'accés de tipus vectorial que detecta l'acció de coalicions de mentiders, que no coneixen el secret, amb una certa probabilitat. La taxa d'informació d'aquest esquema és 1/2, la qual és asímptòticament òptima. Per una estructura de llindar hem proposat un esquema que detecta l'acció de coalicions de mentiders (que sí que coneixen el secret) amb una certa probabilitat. Finalment hem trobat el primer esquema per a una estructura qualsevol que detecta l'acció de coalicions de mentiders (que no coneixen el secret) amb una certa probabilitat.Pel que fa a l'arrel cúbica en el conjunt dels enters mòdul m, hem estudiat l'existència i número d'arrels. Hem generalitzat dos mètodes, dels més potents, pel càlcul de l'arrel quadrada per arrel cúbiques. Aquests són el mètode de Peralta basat en l'ús d'un anell auxiliar i el mètode de Tonelli-Shanks basat en l'ús de subgrups de Sylow. S'ha adjuntat algun comentari per les aplicacions criptogràfiques de les arrels cúbiques. / This thesis is mainly devoted to the study of information rate of secret sharing schemes as well as secret sharing schemes secures against the action of cheaters. As a complement we have studied the problem of cube roots in Z_m.In the first part of our work we study some access structures in a combinatorial way and the boundness of the optimal information rate. We begin with weighted threshold access structures. We state that any of them can be defined with positive integer weights and threshold. We characterize all the rank 2 weighted threshold access structures as a k-graphs, finding minimum integer weights and threshold. We bound the optimal information rate using the complete multipartite covering technique. We extend the above results on characterization and computation of minimum weights and threshold to dual structures after proving the fact that the dual of a weighted threshold structure is a weighted threshold structure. The second family of structures that we studied is the bipartite access structures. We characterize completely the bipartite access structures that can be realized by an ideal secret sharing scheme. We prove that in a bipartite access structure it is equivalent ideal structure, vector space structure and optimal information rate of the structure less than 2/3. Both upper and lower bounds on the optimal information rate of bipartite access structures are given. We also start the general study of multipartite access structure.Using results on bipartite structures we study the information rate of secret sharing schemes whose access structure is defined by two weights and a threshold of arbitrary rank. Some upper and lower bounds are found. Case on more than two weights is considered too.The last family of access structure that we have studied is the homogeneous access structure. We describe two constructions of secret sharing schemes for a such a general class of structures. The first one has a worst information rate than the second one, but on the other hand the size of the secret set is more moderate than the first one. We describe the comparison between our lower bounds on the optimal information rate and on the optimal average information rate as well as comparison with known upper bounds. The results are that our second one are better than the first one and that our bounds are better than the known bound almost for every structure.We have started a study of the upper bounds on the optimal information rate for rank 3 homogenous access structures. We describe a structure that its upper bound is not so far than the lower bound obtained with our second construction.Concerning to the extended capabilities we have studied the schemes secures against the action of cheaters. We have generalized the concepts of secure scheme and robust scheme to any access structure, that several authors have already defined only for threshold structures. We found that for a secure scheme the optimal information rate is upper bounded and we find the bound. We construct a 1/q-secure scheme (for q secrets) asymptotically optimal for a vector space access structure. We compare this scheme with the scheme of Ogata and Kurosawa. Our second scheme is robust realizing a (r,n) threshold structure with probability <= (2r-3)/(q-r). The information rate is 1/3. Finally we propose the first 1/q-secure scheme for any access structure.We have generalized two of the fastest algorithms to take square roots to cube roots in Z_p. The first one is Peralta's algorithm, a probabilistic algorithm based on some properties of a ring. The non probabilistic part of the algorithm runs in log^3 p. The second one is Tonelli-Shanks' algorithm, a probabilistic method based on group theory which runs in log^4 p.

Digital signatures are one of the most important consequences of the appearance of public key cryptography, in 1976. These schemes provide authentication, integrity and non-repudiation to digital communications. Some extensions or variations of the concept of digital signature have been introduced, and many specific realizations of these new types of nature schemes have been proposed.In this thesis, we deal with the basic definitions and required security properties of traditional signature schemes and two of its extensions: distributed signature schemes and ring signature schemes. We review the state of the art in these two topics; then we propose and analyze new specific schemes for different scenarios.Namely, we first study distributed signature schemes for general access structures, based on RSA; then we show that such schemes can be used to construct other cryptographic protocols: distributed key distribution schemes and metering schemes. With respect to ring signatures, we opose schemes for both a scenario where the keys are of the Discrete Logarithm type and a scenario where the public keys of users are inferred from their personal identities. Finally, we also propose some distributed ring signature schemes, a kind of schemes which combine the concepts of distributed signatures and ring signatures. We formally prove the security of all these proposals, assuming that some mathematical problems are hard to solve. Specifically, we base the security of our schemes in the hardness of either the RSA problem, or the Discrete Logarithm problem, or the Computational Diffie-Hellman problem.