Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Tabulation of cubic function fields via polynomial binary cubic forms


Authors: Pieter Rozenhart, Michael Jacobson Jr. and Renate Scheidler
Journal: Math. Comp. 81 (2012), 2335-2359
MSC (2010): Primary 11Y40, 11R16; Secondary 11R58
DOI: https://doi.org/10.1090/S0025-5718-2012-02591-9
Published electronically: March 14, 2012
MathSciNet review: 2945159
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present a method for tabulating all cubic function fields over $ \mathbb{F}_q(t)$ whose discriminant $ D$ has either odd degree or even degree and the leading coefficient of $ -3D$ is a non-square in $ \mathbb{F}_{q}^*$, up to a given bound $ B$ on $ \deg (D)$. Our method is based on a generalization of Belabas' method for tabulating cubic number fields. The main theoretical ingredient is a generalization of a theorem of Davenport and Heilbronn to cubic function fields, along with a reduction theory for binary cubic forms that provides an efficient way to compute equivalence classes of binary cubic forms. The algorithm requires $ O(B^4 q^B)$ field operations as $ B \rightarrow \infty $. The algorithm, examples and numerical data for $ q=5,7,11,13$ are included.


References [Enhancements On Off] (What's this?)

  • 1. E. Artin, Quadratische Körper im Gebiete der höheren Kongruenzen I, Math. Zeitschrift 19 (1924), 153-206. MR 1544651
  • 2. E. Bach and J. Shallit, Algorithmic Number Theory. Vol. 1: Efficient Algorithms, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. MR 1406794 (97e:11157)
  • 3. K. Belabas, A fast algorithm to compute cubic fields, Math. Comp. 66 (1997), no. 219, 1213-1237. MR 1415795 (97m:11159)
  • 4. K. Belabas, On quadratic fields with large $ 3$-rank, Math. Comp. 73 (2004), no. 248, 2061-2074. MR 2059751 (2005c:11132)
  • 5. W.E.H. Berwick and G.B. Mathews, On the reduction of arithmetical binary cubics which have negative discriminant, Proc. of the London Math. Soc., 10 (1912), 48-53.
  • 6. M. Bhargava, The density of discriminants of quartic rings and fields, Annals of Math. Second Series 162 (2005), no. 2, 1031-1063. MR 2183288 (2006m:11163)
  • 7. J. Buchmann and U. Vollmer, Binary Quadratic Forms: An Algorithmic Approach, Algorithms and Computation in Mathematics 20. Springer, Berlin, 2007. MR 2300780 (2008b:11046)
  • 8. D.A. Buell, Binary Quadratic Forms - Classical Theory and Modern Computations, Springer-Verlag, New York, 1989. MR 1012948 (92b:11021)
  • 9. R. Casse, Projective Geometry: An Introduction, Oxford University Press, Oxford, 2006. MR 2264641 (2007f:51001)
  • 10. H. Cohen, Advanced Topics in Computational Number Theory, Springer-Verlag, New York, 2000. MR 1728313 (2000k:11144)
  • 11. R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, First Edition, Springer, New York, 2001. MR 1821158 (2002a:11007)
  • 12. J.E. Cremona, Reduction of binary cubic and quartic forms, LMS J. Comput. Math. 2 (1999), 62-92. MR 1693411 (2000f:11040)
  • 13. B. Datskovsky and D.J. Wright, Density of discriminants of cubic extensions, J. Reine Angew. Math. 386 (1988), 116-138. MR 936994 (90b:11112)
  • 14. H. Davenport and H. Heilbronn, On the density of discriminants of cubic fields I, Bull. London Math. Soc. 1 (1969), 345-348. MR 0254010 (40:7223)
  • 15. H. Davenport and H. Heilbronn, On the density of discriminants of cubic fields II, Proc. Royal Soc. London A 322 (1971), 405-420. MR 0491593 (58:10816)
  • 16. J.S. Ellenberg and A. Venkatesh, Counting extensions of function fields with bounded discriminant and specified Galois group, In Geometric Methods in Algebra and Number Theory, Progress in Mathematics 235, 151-168, Birkhäuser Boston, Boston, MA, 2005. MR 2159381 (2006f:11139)
  • 17. J.S. Ellenberg and A. Venkatesh, The number of extensions of a number field with fixed degree and bounded discriminant, Annals of Math. Second Series, 163 (2006), no. 2, 723-741. MR 2199231 (2006j:11159)
  • 18. A. Enge, How to distinguish hyperelliptic curves in even characteristic, Public-Key Cryptography and Computational Number Theory, De Gruyter, Berlin, 2001, 49-58. MR 1881626 (2002k:11095)
  • 19. J.W.P. Hirschfeld, Projective Geometries Over Finite Fields, Second Edition, Oxford Mathematical Monographs, Oxford University Press, New York, 1998. MR 1612570 (99b:51006)
  • 20. M.J. Jacobson, Jr., Y. Lee, R. Scheidler and H. Williams, Construction of all cubic function fields of a given square-free discriminant, preprint.
  • 21. E. Landquist, P. Rozenhart, R. Scheidler, J. Webster and Q. Wu, An explicit treatment of cubic function fields with applications, Canadian J. Math., 62 (2010), no. 4, 787-807, available online at http://www.cms.math.ca/10.4153/CJM-2010-032-0. MR 2674701 (2011f:14044)
  • 22. R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge University Press, Cambridge, 1994. MR 1294139 (95f:11098)
  • 23. G. B. Mathews, On the reduction and classification of binary cubics which have a negative discriminant, Proc. of the London Math. Soc., 10 (1912), 128-138.
  • 24. M. Rosen, Number Theory in Function Fields, Springer-Verlag, New York, 2002. MR 1876657 (2003d:11171)
  • 25. P. Rozenhart, Fast Tabulation of Cubic Function Fields, Ph.D. Thesis, University of Calgary, 2009.
  • 26. P. Rozenhart and R. Scheidler, Tabulation of cubic function fields with imaginary and unusual Hessian, Proc.Eighth Algorithmic Number Theory Symposium ANTS-VIII, In Lecture Notes in Computer Science 5011, 357-370, Springer, 2008. MR 2467858 (2009m:11213)
  • 27. P. Rozenhart, M.J. Jacobson, Jr., and R. Scheidler, Computing quadratic function fields with high $ 3$-rank via cubic field tabulation, preprint.
  • 28. R. Scheidler, Algorithmic aspects of cubic function fields, Proc. Sixth Algorithmic Number Theory Symposium ANTS-VI, In Lecture Notes in Computer Science 3076, 395-410, Springer, 2004. MR 2138010 (2006c:11136)
  • 29. V. Shoup, NTL: A Library for Doing Number Theory, Software, 2001, see http://www.shoup.net/ntl.
  • 30. H. Stichtenoth, Algebraic Function Fields and Codes, Second Edition, Springer-Verlag, New York, 2009. MR 2464941 (2010d:14034)
  • 31. T. Taniguchi, Distributions of discriminants of cubic algebras, Preprint, Available from http://arxiv.org/abs/math.NT/0606109 (2006).

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y40, 11R16, 11R58

Retrieve articles in all journals with MSC (2010): 11Y40, 11R16, 11R58


Additional Information

Pieter Rozenhart
Affiliation: Department of Mathematics and Statistics, University of Calgary, 2500 University Drive NW, Calgary, Alberta, T2N 1N4, Canada
Email: pmrozenh@alumni.uwaterloo.ca

Michael Jacobson Jr.
Affiliation: Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, Alberta, T2N 1N4, Canada
Email: jacobs@cpsc.ucalgary.ca

Renate Scheidler
Affiliation: Department of Mathematics and Statistics, University of Calgary, 2500 University Drive NW, Calgary, Alberta, T2N 1N4, Canada
Email: rscheidl@math.ucalgary.ca

DOI: https://doi.org/10.1090/S0025-5718-2012-02591-9
Keywords: Computational number theory, cubic function fields, field tabulation
Received by editor(s): April 27, 2010
Received by editor(s) in revised form: May 30, 2011
Published electronically: March 14, 2012
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society