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

• Autores: Javier Valera Martín
• Directores de la Tesis: Josep Maria Miret Biosca (dir. tes.) , Mireille Fouquet (codir. tes.)
• Lectura: En la Universitat de Lleida ( España ) en 2017
• Idioma: español
• Tribunal Calificador de la Tesis: Juan Gabriel Tena Ayuso (presid.) , Magda Valls Marsal (secret.) , Luis Hernández Encinas (voc.)
• Enlaces
  • Tesis en acceso abierto en: TDX
• Resumen
  • español

    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 él. Por lo que se sabe hasta ahora, la validez para el ECDLP de una curva elíptica $ E $ definida sobre un cuerpo finito $ \F_q $ depende de su cardinal sobre $ \F_q $. 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 $ \F_q $. Para ello lo único que tenemos que hacer es calcular curvas elípticas $ d $--isógenas a $ E $ sobre $ \F_q $, es decir, debemos calcular $ d $--isogenias $ \F_q $--racionales.

    Sea $ \ell $ un número primo tal que $ \ell $ no divide a $ q $. El conjunto de todas las clases de isomorfía sobre $ \F_q $ de curvas elípticas ordinarias con un determinado cardinal sobre $ \F_q $ puede ser representado mediante un grafo dirigido cuyos vértices son las clases de isomorfía y cuyos arcos representan $ \ell $--isogenias $ \F_q $--racionales entre curvas elípticas de los vértices. Cada componente conexa de este digrafo es un volcán de $ \ell $--isogenias o $ \ell $--volcán sobre $ \F_q $. Los vértices de un $ \ell $--volcán se distribuyen por niveles. El número total de niveles menos uno es su altura. Calcular la altura de un $ \ell $--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 aplicaciones de los volcanes de $ \ell $--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 $ \ell $--volcanes.

    En esta tesis, por un lado, damos nuevos métodos para recorrer los vértices de los volcanes de $ \ell $--isogenias. Por otro lado, conocida la valoración $ \ell $--ádica del cardinal de $ E $ sobre $ \F_q $, estudiamos la valoración $ \ell $--ádica del cardinal de $ E $ sobre una extensión de grado $ k $ de $ \F_q $. Conocida la estructura del subgrupo de $ \ell $--Sylow de $ E $ sobre $ \F_q $, también estudiamos la del subgrupo de $ \ell $--Sylow de $ E $ sobre $ \F_{q^k} $.

  • English

    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 $ \F_q $ depends on its cardinality over $ \F_q $. 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 $ \F_q $--rational $ d $--isogenies of $ E $, where $ d $ is a positive integer.

    Let $ \ell $ be a prime number such that $ \ell $ does not divide $ q $. The set of all $ \F_q $--isomorphism classes of ordinary elliptic curves with a given group order over $ \F_q $ can be represented as a directed graph whose vertices are the $ \F_q $--isomorphism classes and whose arcs represent $ \F_q $--rational $ \ell $--isogenies. Each connex component of this graph is a volcano of $ \ell $--isogenies or $ \ell $--volcano over $ \F_q $. The vertices of a volcano of $ \ell $--isogenies can be stratified into levels. The number of levels minus one is called the height of the $ \ell $--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 $ \ell $--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 $ \ell $--volcanoes.

    In this thesis, on one hand, we give new methods to go through the vertices of the $ \ell $--volcanoes. On the other hand, assuming the knowledge of the $ \ell $--adic valuation of the cardinality of $ E $ over $ \F_q $, we study the $ \ell $--adic valuation of the cardinality of $ E $ over an extension of degree $ k $ over $ \F_q $. Assuming the structure of the $ \ell $--Sylow subgroup of $ E $ over $ \F_q $ is known, we also study the structure of the $ \ell $--Sylow subgroup of $ E $ over $ \F_{q^k} $.

  • català

    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 $ \F_q $ depèn del seu cardinal sobre $ \F_q $. 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 $ \F_q $. Per dur a terme aquesta tasca només hem de calcular corbes el.líptiques $ d $--isògenes a $ E $ sobre $ \F_q $, és a dir, hem de calcular $ d $--isogènies $ \F_q $--racionals.

    Sigui $ \ell $ un nombre primer tal que $ \ell $ no divideix a $ q $. El conjunt de totes les classes d'isomorfia sobre $ \F_q $ de corbes el.líptiques ordinàries amb un determinat cardinal sobre $ \F_q $ pot ser representat mitjançant un graf dirigit on els vèrtexs són les classes d'isomorfia i on els arcs representen $ \ell $--isogènies $ \F_q $--racionals entre corbes el.líptiques dels vèrtexs. Cada component connexa d'aquest digraf és un volcà de $ \ell $--isogènies o $ \ell $--volcà sobre $ \F_q $. Els vèrtexs d'un $ \ell $--volcà es distribueixen per nivells. El nombre total de nivells menys un és la seva altura. Calcular l'altura d'un $ \ell $--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 $ \ell $--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 $ \ell $--volcans.

    En aquesta tesi, per una banda, donem nous métodes per recórrer els vèrtexs dels volcans de $ \ell $--isogènies. Per l'altra, coneguda la valoració $ \ell $--àdica del cardinal de $ E $ sobre $ \F_q $, estudiem la valoració $ \ell $--àdica del cardinal de $ E $ sobre una extensió de grau $ k $ de $ \F_q $. Coneguda l'estructura del subgrup de $ \ell $--Sylow de $ E $ sobre $ \F_q $, també estudiem la del subgrup de $ \ell $--Sylow de $ E $ sobre $ \F_{q^k} $.