Contribuciones a la cardinalidad de curvas elípticas y a los volcanes de isogenias

Abstract

Avui en dia, un dels problemes matemàtics més utilitzats a l’hora de dissenyar protocols criptogràfics és el problema del logaritme discret sobre el grup de punts d’una corba el.líptica definida sobre un cos finit (ECDLP – Elliptic Curve Discrete Logarithm Problem). No obstant, no totes les corbes el.líptiques existents són vàlides per a aquest problema. Pel que se sap fins ara, la validesa per al ECDLP d’una corba el.líptica E definida sobre un cos finit Fq depèn del seu cardinal sobre Fq. Donat que el càlcul del cardinal de E és un problema computacionalment costós, sembla raonable pensar que si E és vàlida, puguem obtenir a partir d’ella altres corbes el.líptiques que també ho siguin, és a dir, que també tinguin el seu mateix cardinal sobre Fq. Per dur a terme aquesta tasca nom´es hem de calcular corbes el.líptiques d–isògenes a E sobre Fq, és a dir, hem de calcular d–isogènies Fq–racionals. Sigui ℓ un nombre primer tal que ℓ no divideix a q. El conjunt de totes les classes d’isomorfia sobre Fq de corbes el.líptiques ordinàries amb un determinat cardinal sobre Fq pot ser representat mitjan¸cant un graf dirigit on els vèrtexs són les classes d’isomorfia i on els arcs representen ℓ–isogènies Fq–racionals entre corbes el.líptiques dels vèrtexs. Cada component connexa d’aquest digraf és un volcà de ℓ–isogènies o ℓ–volcà sobre Fq. Els vèrtex d’un ℓ–volcà es distribueixen per nivells. El nombre total de nivells menys un és la seva altura. Calcular l’altura d’un ℓ–volcà pot millorar l’eficiència de l’algoritme SEA, sent aquest algoritme el millor conegut fins ara per al càlcul del cardinal d’una corba el.líptica. Altres aplicacions dels volcans de ℓ–isogènies les trobem en el càlcul dels polinomis de classes de Hilbert o dels polinomis modulars. En totes elles cal recórrer els vèrtexs de ℓ–volcans. En aquesta tesi, per una banda, donem nous mètodes per recórrer els vèrtexs dels volcans de ℓ–isogènies. Per l’altra, coneguda la valoració ℓ–àdica del cardinal de E sobre Fq, estudiem la valoració ℓ–àdica del cardinal de E sobre una extensió de grau k de Fq. Coneguda l’estructura del subgrup de ℓ–Sylow de E sobre Fq, també estudiem la del subgrup de ℓ–Sylow de E sobre Fqk .

Aunque uno de los problemas matemáticos más utilizados hoy en día en el diseño de protocolos criptográficos es el problema del logaritmo discreto sobre el grupo de puntos de una curva elíptica definida sobre un cuerpo finito (ECDLP – Elliptic Curve Discrete Logarithm Problem), no todas las curvas elípticas existentes son válidas para su uso en el. Por lo que se sabe hasta ahora, la validez para el ECDLP de una curva elíptica E definida sobre un cuerpo finito Fq depende de su cardinal sobre Fq. Como calcular el cardinal de E es un problema computacionalmente costoso, parece razonable pensar que si E es válida, podamos obtener a partir de ella otras curvas elípticas que también lo sean, es decir, que también tengan su mismo cardinal sobre Fq. Para ello lo único que tenemos que hacer es calcular curvas elípticas d–isógenas a E sobre Fq, es decir, debemos calcular d–isogenias Fq–racionales. Sea ℓ un número primo tal que ℓ no divide a q. El conjunto de todas las clases de isomorfía sobre Fq de curvas elípticas ordinarias con un determinado cardinal sobre Fq puede ser representado mediante un grafo dirigido cuyos vértices son las clases de isomorfía y cuyos arcos representan ℓ–isogenias Fq–racionales entre curvas elípticas de los vértices. Cada componente conexa de este digrafo es un volcán de ℓ–isogenias o ℓ–volcán sobre Fq. Los vértices de un ℓ–volcán se distribuyen por niveles. El número total de niveles menos uno es su altura. Calcular la altura de un ℓ–volcán puede mejorar la eficiencia del algoritmo SEA, siendo el SEA el mejor algoritmo conocido actualmente para calcular el cardinal de una curva elíptica. Otras 4 aplicaciones de los volcanes de ℓ–isogenias las encontramos en el cálculo de los polinomios de clases de Hilbert o los polinomios modulares. En todas ellas es preciso recorrer los vértices de ℓ–volcanes. En esta tesis, por un lado, damos nuevos métodos para recorrer los vértices de los volcanes de ℓ–isogenias. Por otro lado, conocida la valoración ℓ–ádica del cardinal de E sobre Fq, estudiamos la valoración ℓ–ádica del cardinal de E sobre una extensión de grado k de Fq. Conocida la estructura del subgrupo de ℓ–Sylow de E sobre Fq, también estudiamos la del subgrupo de ℓ–Sylow de E sobre Fqk .

One of the most used mathematical problems for the design of modern cryptographic protocols is the discrete logarithm problem over the group of points of an elliptic curve defined over a finite field (ECDLP). However, not all existing elliptic curves are valid for this problem. The validity for the ECDLP of an elliptic curve E defined over a finite field Fq depends on its cardinality over Fq. The computation of the group order of E is an expensive task. Therefore, if E has a “good” cardinality, it seems reasonable to obtain from E other elliptic curves with the same cardinality. For this task, we can compute some Fq–rational d–isogenies of E, where d is a positive integer. Let ℓ be a prime number such that ℓ does not divide q. The set of all Fq–isomorphism classes of ordinary elliptic curves with a given group order over Fq can be represented as a directed graph whose vertices are the Fq–isomorphism classes and whose arcs represent Fq–rational ℓ–isogenies. Each connex component of this graph is a volcano of ℓ–isogenies or ℓ–volcano over Fq. The vertices of a volcano of ℓ–isogenies can be stratified into levels. The number of levels minus one is called the height of the ℓ–volcano. The computation of this value can improve the SEA algorithm (the known best algorithm to compute the cardinality of an elliptic curve). Volcanoes of ℓ–isogenies have also been used to compute the Hilbert class polynomials or to compute the modular polynomials. In all these applications, it is necessary to go through the vertices of ℓ–volcanoes. In this thesis, on one hand, we give new methods to go through the vertices of the ℓ–volcanoes. On the other hand, assuming the knowledge of the ℓ–adic valuation of the cardinality of E over Fq, we study the ℓ–adic valuation of the cardinality of E over an extension of degree k over Fq. Assuming the structure of the ℓ–Sylow subgroup of E over Fq is known, we also study the structure of the ℓ–Sylow subgroup of E over Fqk .