SMF

Un algorithme fondé sur le théorème chinois pour construire des courbes de genre 2 sur des corps finis

A CRT algorithm for constructing genus 2 curves over finite fields

Kirsten Eisenträger, Kristin Lauter
     
                
  • Année : 2011
  • Tome : 21
  • Format : Papier
  • Langue de l'ouvrage :
    Anglais
  • Class. Math. : 11G15, 11G10, 11R37, 14G50
  • Pages : 161-176
Nous présentons une nouvelle méthode pour construire des courbes de genre $2$ sur un corps fini $\mathbb F _n$ avec un nombre donné de points sur sa jacobienne. Cette méthode a des applications importantes en cryptographie, où des groupes d'ordre premier sont employés pour former des cryptosystèmes fondés sur le logarithme discret. Notre algorithme fournit une alternative à la méthode traditionnelle de multiplication complexe pour construire des courbes de genre $2$. Pour un corps quartique $K$ à multiplication complexe de type primitif, nous calculons les polynômes de e d'Igusa modulo $p$ pour certains petits premiers $p$ et employons le théorème chinois et une borne sur les dénominateurs pour construire les polynômes de e. Nous fournissons également un algorithme pour déterminer les anneaux d'endomorphismes des jacobiennes de courbes ordinaires de genre 2 sur des corps finis, généralisant le travail de Kohel pour les courbes elliptiques.
We present a new method for constructing genus $2$ curves over a finite field $\mathbb F _n$ with a given number of points on its Jacobian. This method has important applications in cryptography, where groups of prime order are used as the basis for discrete-log based cryptosystems. Our algorithm provides an alternative to the traditional CM method for constructing genus 2 curves. For a quartic CM field $K$ with primitive CM type, we compute the Igusa polynomials modulo $p$ for certain small primes $p$ and then use the Chinese remainder theorem (CRT) and a bound on the denominators to construct the polynomials. We also provide an algorithm for determining endomorphism rings of ordinary Jacobians of genus 2 curves over finite fields, generalizing the work of Kohel for elliptic curves.
Courbes de genre $2$, anneaux d'endomorphismes, polynômes de e d'Igusa, multiplication complexe, théorème chinois
Genus $2$ curves, endomorphism rings, Igusa polynomials, complex multiplication, Chinese Remainder Theorem