On the discrete logarithm problem for plane curves
Journal de théorie des nombres de Bordeaux, Volume 24 (2012) no. 3, p. 639-667

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 O ˜(q), where q is the cardinality of the ground field. Moreover, it is proven that for every fixed natural number d4 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 O ˜(q 2-2 d-2 ). This holds in particular for curves given by reflexive plane models.

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 O ˜(q) avec un algorithme convenable. En outre, pour chaque entier naturel fixé d4 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 O ˜(q 2-2 d-2 ). Cela vaut en particulier pour les courbes données par des modèles plans réflexifs.

@article{JTNB_2012__24_3_639_0,
     author = {Diem, Claus},
     title = {On the discrete logarithm problem for  plane curves},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {24},
     number = {3},
     year = {2012},
     pages = {639-667},
     doi = {10.5802/jtnb.815},
     mrnumber = {3010633},
     zbl = {1270.11128},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_2012__24_3_639_0}
}
Diem, Claus. On the discrete logarithm problem for  plane curves. Journal de théorie des nombres de Bordeaux, Volume 24 (2012) no. 3, pp. 639-667. doi : 10.5802/jtnb.815. http://www.numdam.org/item/JTNB_2012__24_3_639_0/

[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 2282948 | Zbl 1143.11361

[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 2728990 | Zbl 1231.11142

[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 2814257

[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 2438510 | Zbl 1167.11047

[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 2261032 | Zbl 1179.94062

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

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

[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 895153 | Zbl 0579.14047

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

[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 568897 | Zbl 0385.14018

[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 1298275 | Zbl 0822.11077

[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 2374992 | Zbl 1221.94055

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

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

[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 2093253 | Zbl 1205.94103

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

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

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