On the discrete logarithm problem for plane curves

Diem, Claus

Journal de théorie des nombres de Bordeaux, Tome 24 (2012) no. 3, pp. 639-667.

Dans cet article, on étudie le problème du logarithme discret dans le groupe de classes de degré 0 des courbes données par des modèles plans sur des corps finis. Dénotons le cardinal du corps de base d’une telle courbe par $q$. Il est prouvé que l’expérance du temps de résolution du problème du logarithme discret pour des courbes non-hyperelliptiques de genre 3 (donnée par des modèles plans de degré 4) est de $\tilde{O}\left(q\right)$ avec un algorithme convenable. En outre, pour chaque entier naturel fixé $d\ge 4$ on a le résultat suivant. Considérons le problème du logarithme discret pour les courbes données par des modèles plans de degré $d$ pour lesquels il existe une droite qui définit un diviseur sur la courbe constitué de $d$ points ${𝔽}_q$-rationnels distincts. Alors, il y a un algorithme pour lequel l’espérance du temps de résolution du problème est de $\tilde{O}\left(q^{2-\frac{2}{d-2}}\right)$. Cela vaut en particulier pour les courbes données par des modèles plans réflexifs.

In this article the discrete logarithm problem in degree 0 class groups of curves over finite fields given by plane models is studied. It is proven that the discrete logarithm problem for non-hyperelliptic curves of genus 3 (given by plane models of degree 4) can be solved in an expected time of $\tilde{O}\left(q\right)$, where $q$ is the cardinality of the ground field. Moreover, it is proven that for every fixed natural number $d\ge 4$ the following holds: We consider the discrete logarithm problem for curves given by plane models of degree $d$ for which there exists a line which defines a divisor which splits completely into distinct ${𝔽}_q$-rational points. Then this problem can be solved in an expected time of $\tilde{O}\left(q^{2-\frac{2}{d-2}}\right)$. This holds in particular for curves given by reflexive plane models.

[1] C. Diem, An Index Calculus Algorithm for Plane Curves of Small Degree. In F. Hess, S. Pauli, and M. Pohst, editors, Algorithmic Number Theory — ANTS VII, LNCS 4076, pages 543 – 557, Berlin, 2006. Springer. | MR | Zbl

[2] C. Diem, On arithmetic and the discrete logarithm problem in class groups of curves. Habilitation thesis, 2008.

[3] C. Diem, On the discrete logarithm problem in class groups of curves. Math.Comp. 80 (2011), 443–475. | MR | Zbl

[4] C. Diem, On the notion of bit complexity. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 103 (2011), 35–52. In the “Complexity Column”. | MR

[5] C. Diem and E. Thomé, Index calculus in class groups of non-hyperelliptic curves of genus three. J. Cryptology 21 (2008), 593–611. | MR | Zbl

[6] P. Gaudry, E. Thomé, N. Thériault, and C. Diem, A double large prime variation for small genus hyperelliptic index calculus. Math. Comp. 76 (2007), 475–492. | MR | Zbl

[7] R. Hartshorne, Algebraic Geometry. Springer-Verlag, 1977. | MR | Zbl

[8] A. Hefez, Non-reflexive curves. Compositio Math. 69 (1989), 3–35. | Numdam | MR | Zbl

[9] A. Hefez and S. Kleiman, Notes on the duality of projective varieties. In Geometry today (Rome, 1984), volume 60 of Progr. Math., pages 143–183. Birkhäuser, 1985. | MR | Zbl

[10] F. Heß, Computing Riemann-Roch spaces in algebraic function fields and related topics. J. Symbolic Comput. 33 (2002), 425–445. | MR | Zbl

[11] S. Kleiman, The enumerative theory of singularities. In Real and complex singularities (Proc. Ninth Nordic Summer School/NAVF Sympos. Math., Oslo, 1976), pages 297–396. Sijthoff and Noordhoff, Alphen aan den Rijn, 1977. | MR | Zbl

[12] V.K. Murty and J. Scherk, Effective versions of the Chebotarev density theorem for funciton fields. C. R. Acad. Sci. 319 (1994), 523–528. | MR | Zbl

[13] K. Nagao, Index calculus attack for Jacobian of hyperelliptic curves of small genus using two large primes. Japan J. Indust. Appl. Math. 24 (2007), 289–305. | MR | Zbl

[14] J. Neukirch, Algebraische Zahlentheorie. Springer-Verlag, 1991. | MR | Zbl

[15] J. Pila, Frobenius maps of abelian varieties and fining roots of unity in finite fields. Math. Comp. 55 (1990), 745–763. | MR | Zbl

[16] J. Pila, Counting points on curves over families in polynomial time. Available on the arXiv under math.NT/0504570, 1991.

[17] N. Thériault, Index calculus attack for hyperelliptic curves of small genus. In Advances in Cryptology — ASIACRYPT 2003, volume 2894 of LNCS, pages 75–92. Springer-Verlag, 2003. | MR | Zbl

[18] R. Walker, Algebraic Curves. Springer-Verlag, 1978. | MR | Zbl

[19] A. Wallace, Tangency and duality over arbitrary fields. Proc. Lond. Math. Soc. (3) 6 (1956), 321–342. | MR | Zbl

[20] H. Wieland, Finite Permutation Groups. Academic Press, New York, 1964. | MR | Zbl