On the discrete logarithm problem for plane curves
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 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.

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.

DOI : 10.5802/jtnb.815
Diem, Claus 1

1 Université de Leipzig Augustusplatz 10 04109 Leipzig Allemagne
@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},
     pages = {639--667},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {24},
     number = {3},
     year = {2012},
     doi = {10.5802/jtnb.815},
     zbl = {1270.11128},
     mrnumber = {3010633},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/jtnb.815/}
}
TY  - JOUR
AU  - Diem, Claus
TI  - On the discrete logarithm problem for  plane curves
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2012
SP  - 639
EP  - 667
VL  - 24
IS  - 3
PB  - Société Arithmétique de Bordeaux
UR  - http://www.numdam.org/articles/10.5802/jtnb.815/
DO  - 10.5802/jtnb.815
LA  - en
ID  - JTNB_2012__24_3_639_0
ER  - 
%0 Journal Article
%A Diem, Claus
%T On the discrete logarithm problem for  plane curves
%J Journal de théorie des nombres de Bordeaux
%D 2012
%P 639-667
%V 24
%N 3
%I Société Arithmétique de Bordeaux
%U http://www.numdam.org/articles/10.5802/jtnb.815/
%R 10.5802/jtnb.815
%G en
%F JTNB_2012__24_3_639_0
Diem, Claus. On the discrete logarithm problem for  plane curves. Journal de théorie des nombres de Bordeaux, Tome 24 (2012) no. 3, pp. 639-667. doi : 10.5802/jtnb.815. http://www.numdam.org/articles/10.5802/jtnb.815/

[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

Cité par Sources :