# On the discrete logarithm problem for plane curves

Claus Diem^{[1]}

- [1] Université de Leipzig Augustusplatz 10 04109 Leipzig Allemagne

Journal de Théorie des Nombres de Bordeaux (2012)

- Volume: 24, Issue: 3, page 639-667
- ISSN: 1246-7405

## Access Full Article

top## Abstract

top## How to cite

topDiem, Claus. "On the discrete logarithm problem for plane curves." Journal de Théorie des Nombres de Bordeaux 24.3 (2012): 639-667. <http://eudml.org/doc/251058>.

@article{Diem2012,

abstract = {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\}(q)$, 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 $\mathbb\{F\}_q$-rational points. Then this problem can be solved in an expected time of $\tilde\{O\}(q^\{2 - \frac\{2\}\{d-2\}\})$. This holds in particular for curves given by reflexive plane models.},

affiliation = {Université de Leipzig Augustusplatz 10 04109 Leipzig Allemagne},

author = {Diem, Claus},

journal = {Journal de Théorie des Nombres de Bordeaux},

keywords = {discrete logarithm; curves over finite fields; index calculus; reflexive curve},

language = {eng},

month = {11},

number = {3},

pages = {639-667},

publisher = {Société Arithmétique de Bordeaux},

title = {On the discrete logarithm problem for plane curves},

url = {http://eudml.org/doc/251058},

volume = {24},

year = {2012},

}

TY - JOUR

AU - Diem, Claus

TI - On the discrete logarithm problem for plane curves

JO - Journal de Théorie des Nombres de Bordeaux

DA - 2012/11//

PB - Société Arithmétique de Bordeaux

VL - 24

IS - 3

SP - 639

EP - 667

AB - 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}(q)$, 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 $\mathbb{F}_q$-rational points. Then this problem can be solved in an expected time of $\tilde{O}(q^{2 - \frac{2}{d-2}})$. This holds in particular for curves given by reflexive plane models.

LA - eng

KW - discrete logarithm; curves over finite fields; index calculus; reflexive curve

UR - http://eudml.org/doc/251058

ER -

## References

top- 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. Zbl1143.11361MR2282948
- C. Diem, On arithmetic and the discrete logarithm problem in class groups of curves. Habilitation thesis, 2008.
- C. Diem, On the discrete logarithm problem in class groups of curves. Math.Comp. 80 (2011), 443–475. Zbl1231.11142MR2728990
- C. Diem, On the notion of bit complexity. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 103 (2011), 35–52. In the “Complexity Column”. Zbl1258.68057MR2814257
- C. Diem and E. Thomé, Index calculus in class groups of non-hyperelliptic curves of genus three. J. Cryptology 21 (2008), 593–611. Zbl1167.11047MR2438510
- 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. Zbl1179.94062MR2261032
- R. Hartshorne, Algebraic Geometry. Springer-Verlag, 1977. Zbl0531.14001MR463157
- A. Hefez, Non-reflexive curves. Compositio Math. 69 (1989), 3–35. Zbl0706.14024MR986811
- 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. Zbl0579.14047MR895153
- F. Heß, Computing Riemann-Roch spaces in algebraic function fields and related topics. J. Symbolic Comput. 33 (2002), 425–445. Zbl1058.14071MR1890579
- 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. Zbl0385.14018MR568897
- V.K. Murty and J. Scherk, Effective versions of the Chebotarev density theorem for funciton fields. C. R. Acad. Sci. 319 (1994), 523–528. Zbl0822.11077MR1298275
- 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. Zbl1221.94055MR2374992
- J. Neukirch, Algebraische Zahlentheorie. Springer-Verlag, 1991. Zbl0747.11001MR1085974
- J. Pila, Frobenius maps of abelian varieties and fining roots of unity in finite fields. Math. Comp. 55 (1990), 745–763. Zbl0724.11070MR1035941
- J. Pila, Counting points on curves over families in polynomial time. Available on the arXiv under math.NT/0504570, 1991.
- 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. Zbl1205.94103MR2093253
- R. Walker, Algebraic Curves. Springer-Verlag, 1978. Zbl0399.14016MR513824
- A. Wallace, Tangency and duality over arbitrary fields. Proc. Lond. Math. Soc. (3) 6 (1956), 321–342. Zbl0072.16002MR80354
- H. Wieland, Finite Permutation Groups. Academic Press, New York, 1964. Zbl0138.02501MR183775

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.