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

Abstract

top
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 d ≥ 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 O ˜ ( q 2 - 2 d - 2 ) . This holds in particular for curves given by reflexive plane models.

How to cite

top

Diem, 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
  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. Zbl1143.11361MR2282948
  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. Zbl1231.11142MR2728990
  4. 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
  5. 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
  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. Zbl1179.94062MR2261032
  7. R. Hartshorne, Algebraic Geometry. Springer-Verlag, 1977. Zbl0531.14001MR463157
  8. A. Hefez, Non-reflexive curves. Compositio Math. 69 (1989), 3–35. Zbl0706.14024MR986811
  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. Zbl0579.14047MR895153
  10. F. Heß, Computing Riemann-Roch spaces in algebraic function fields and related topics. J. Symbolic Comput. 33 (2002), 425–445. Zbl1058.14071MR1890579
  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. Zbl0385.14018MR568897
  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. Zbl0822.11077MR1298275
  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. Zbl1221.94055MR2374992
  14. J. Neukirch, Algebraische Zahlentheorie. Springer-Verlag, 1991. Zbl0747.11001MR1085974
  15. J. Pila, Frobenius maps of abelian varieties and fining roots of unity in finite fields. Math. Comp. 55 (1990), 745–763. Zbl0724.11070MR1035941
  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. Zbl1205.94103MR2093253
  18. R. Walker, Algebraic Curves. Springer-Verlag, 1978. Zbl0399.14016MR513824
  19. A. Wallace, Tangency and duality over arbitrary fields. Proc. Lond. Math. Soc. (3) 6 (1956), 321–342. Zbl0072.16002MR80354
  20. H. Wieland, Finite Permutation Groups. Academic Press, New York, 1964. Zbl0138.02501MR183775

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.