Glasnik Matematicki, Vol. 44, No.1 (2009), 89-126.

EXPLICIT INFRASTRUCTURE FOR REAL QUADRATIC FUNCTION FIELDS AND REAL HYPERELLIPTIC CURVES

Andreas Stein

Institut für Mathematik, Carl-von-Ossietzky Universität Oldenburg, D-26111 Oldenburg, Germany
e-mail: andreas.stein1@uni-oldenburg.de

Abstract.   In 1989, Koblitz first proposed the Jacobian of a an imaginary hyperelliptic curve for use in public-key cryptographic protocols. This concept is a generalization of elliptic curve cryptography. It can be used with the same assumed key-per-bit strength for small genus. More recently, real hyperelliptic curves of small genus have been introduced as another source for cryptographic protocols. The arithmetic is more involved than its imaginary counterparts and it is based on the so-called infrastructure of the set of reduced principal ideals in the ring of regular functions of the curve. This infrastructure is an interesting phenomenon. The main purpose of this article is to explain the infrastructure in explicit terms and thus extend Shanks' infrastructure ideas in real quadratic number fields to the case of real quadratic congruence function fields and their curves. Hereby, we first present an elementary introduction to the continued fraction expansion of real quadratic irrationalities and then generalize important results for reduced ideals.

2000 Mathematics Subject Classification.   11R58, 11Y16, 11Y65, 11M38.

Key words and phrases.   Real hyperelliptic function field, real hyperelliptic curve, infrastructure and distance, reduced ideals, regulator, continued fraction expansion.

Full text (PDF) (free access)

DOI: 10.3336/gm.44.1.05

References:

  1. W. W. Adams and M. J. Razar, Multiples of points on elliptic curves and continued fractions, Proc. London Math. Soc. (3) 41 (1980), 481-498.
    MathSciNet     CrossRef

  2. E. Artin, Quadratische Körper im Gebiete der höheren Kongruenzen I, Math. Z. 19 (1924), 153-206.
    MathSciNet     CrossRef

  3. E. Artin, Quadratische Körper im Gebiete der höheren Kongruenzen II, Math. Z. 19 (1924), 207-246.
    MathSciNet     CrossRef

  4. H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, Berlin, 1993.
    MathSciNet

  5. H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen and F. Vercouteren, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Discrete Mathematics and Its Applications 34, Chapman & Hall/CRC, Boca Raton, 2006.
    MathSciNet

  6. M. Deuring, Lectures on the Theory of Algebraic Functions of One Variable, Lecture Notes in Mathematics 314, Springer-Verlag, Berlin-Heidelberg, 1973.
    MathSciNet

  7. A. Enge, How to distinguish hyperelliptic curves in even characteristic, in: Public-Key Cryptography and Computational Number Theory, eds. K. Alster, J. Urbanowicz, and H. C. Williams, De Gruyter, Berlin, 2001, 49-58.
    MathSciNet

  8. S. Erickson, M. J. Jacobson, Jr., N. Shang, S. Shen and A. Stein, Explicit formulas for real hyperelliptic curves of genus 2 in affine representation, in: International Workshop on the Arithmetic of Finite Fields - WAIFI 2007, Lect. Notes Comput. Sci. 4547, Springer-Verlag, (2007), 202-218.
    MathSciNet

  9. S. K. Gogia and I. S. Luthar, The Brauer-Siegel theorem for algebraic function fields, J. Reine Angew. Math. 299/300 (1978), 28-37.
    MathSciNet

  10. M. J. Jacobson, Jr., A. J. Menezes and A. Stein, Hyperelliptic curves and cryptography, in: High Primes and Misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams, Fields Institute Communications 41, American Mathematical Society, 2004, 255-282.
    MathSciNet

  11. M. J. Jacobson, Jr., R. Scheidler and A. Stein, Fast arithmetic on hyperelliptic curves via continued fraction expansions, in: Advances in Coding Theory and Cryptology, volume 3 of Series on Coding Theory and Cryptology 2, eds. T. Shaska, W. C. Huffman, D. Joyner, and V. Ustimenko, World Scientific Publishing Co. Pte. Ltd., Hackensack, New Jersey, 2007, 201-244.

  12. M. J. Jacobson, Jr., R. Scheidler and A. Stein, Cryptographic protocols on real hyperelliptic curves, Adv. Math. Commun. 1 (2007), 197-221.
    MathSciNet     CrossRef

  13. P. Kaplan and K. S. Williams, The distance between ideals in the orders of a real quadratic field, Enseign. Math. (2) 36 (1990), 321-358.
    MathSciNet

  14. N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), 139-150.
    MathSciNet     CrossRef

  15. T. Lange, Formulae for arithmetic on genus 2 hyperelliptic curves, Appl. Algebra Engrg. Comm. Comput. 15 (2005), 295-328.
    MathSciNet     CrossRef

  16. H. W. Lenstra, Jr., On the calculation of regulators and class numbers of quadratic fields, London. Math. Soc. Lecture Note Ser. 56 (1982), 123-150.
    MathSciNet

  17. D. Lorenzini, An invitation to arithmetic geometry, Graduate Studies in Mathematics 9, AMS, Providence, 1996.
    MathSciNet

  18. A. J. Menezes, Y. Wu and R. J. Zuccherato, An elementary introduction to hyperelliptic curves, in: Koblitz, N.: Algebraic Aspects of Cryptography, Springer-Verlag, Berlin Heidelberg New York, 1998, 155-178.
    MathSciNet

  19. S. Paulus and H.-G. Rück, Real and imaginary quadratic representations of hyperelliptic function fields, Math. Comp. 68 (1999), 1233-1241.
    MathSciNet     CrossRef

  20. O. Perron, Die Lehre von den Kettenbrüchen, Teubner, Leipzig, 1913.

  21. K. H. Rosen, Elementary Number Theory and its Applications, Addison Wesley Publishing Company, Reading, 1993.
    MathSciNet

  22. M. Rosen, Number Theory in Function Fields, Springer-Verlag, New York, 2002.
    MathSciNet

  23. R. Scheidler, A. Stein and H. C. Williams, Key-exchange in real quadratic congruence function fields, Des. Codes and Cryptogr. 7 (1996), 153-174.
    MathSciNet     CrossRef

  24. R. Scheidler and A. Stein, Class number approximation in cubic function fields, Contrib. Discrete Math. 2 (2007), 107-132.
    MathSciNet

  25. F. K. Schmidt, Analytische Zahlentheorie in Körpern der Charakteristik p, Math. Z. 33 (1931), 1-32.
    MathSciNet     CrossRef

  26. D. Shanks, Class number, a theory of factorization and genera, in: Proc. Symp. Pure Math. 20, 1969, AMS, Providence, 1971, 415-440.
    MathSciNet

  27. D. Shanks, The infrastructure of a real quadratic field and its applications, in: Proceedings of the Number Theory Conference, Boulder, Colo., 1972, 217-224.
    MathSciNet

  28. A. Stein, Baby step-giant step-verfahren in reell-quadratischen kongruenzfunktionenkörpern mit charakteristik ungleich 2, Master's thesis, Universität des Saarlandes, Saarbrücken, Germany, 1992.

  29. A. Stein, Equivalences between elliptic curves and real quadratic congruence function fields, J. Théor. Nombres Bordeaux 9 (1997), 75-95.
    MathSciNet     Cedram

  30. A. Stein, Sharp upper bounds for arithmetics in hyperelliptic function fields, J. Ramanujan Math. Soc. 16 (2001), 119-203.
    MathSciNet

  31. A. Stein and E. Teske, Explicit bounds and heuristics on class numbers in hyperelliptic function fields, Math. Comp. 71 (2002), 837-861.
    MathSciNet     CrossRef

  32. A. Stein and H. C. Williams, An improved method of computing the regulator of a real quadratic function field, in: Algorithmic Number Theory ANTS-III, Lecture Notes in Computer Science 1423, Springer, Berlin, 1998, 607-620.
    MathSciNet

  33. A. Stein and H. C. Williams, Some methods for evaluating the regulator of a real quadratic function field, Experiment. Math. 8 (1999), 119-133.
    MathSciNet    

  34. A. Stein and H. G. Zimmer, An algorithm for determining the regulator and the fundamental unit of a hyperelliptic congruence function field, in: Proc. 1991 Int. Symp. on Symbolic and Algebraic Computation, ISAAC, Bonn, July 15-17, pages 183-184, ACM Press, 1991.

  35. A. Stein and E. Teske, The parallelized Pollard kangaroo method in real quadratic function fields, Math. Comp. 71 (2002), 793-814.
    MathSciNet     CrossRef

  36. A. J. Stephens and H. C. Williams, Computation of real quadratic fields with class number one, Math. Comp. 51 (1988), 809-824.
    MathSciNet     CrossRef

  37. A. J. Stephens and H. C. Williams, Some computational results on a problem concerning powerful numbers, Math. Comp. 50 (1988), 619-632.
    MathSciNet     CrossRef

  38. H. Stichtenoth, Algebraic Function Fields and Codes, Springer-Verlag, Berlin, 1993.
    MathSciNet

  39. B. Weis and H. G. Zimmer, Artin's Theorie der quadratischen Kongruenzfunktionenkörper und ihre Anwendung auf die Berechnung der Einheiten- und Klassengruppen, Mitt. Math. Ges. Hamburg XII (1991), 261-286.
    MathSciNet

  40. E. Weiss, Algebraic Number Theory, McGraw-Hill Book Co., Inc., New York-San Francisco-Toronto-London, 1963.
    MathSciNet

  41. H. C. Williams and M. C. Wunderlich, On the parallel generation of the residues for the continued fraction algorithm, Math. Comp. 48 (1987), 405-423.
    MathSciNet     CrossRef

  42. R. J. Zuccherato, The continued fraction algorithm and regulator for quadratic function fields of characteristic 2, J. Algebra 190 (1997), 563-587.
    MathSciNet     CrossRef

  43. R. J. Zuccherato, New applications of elliptic curves and function fields in cryptography, PhD thesis, Department of Combinatorics and Optimization, University of Waterloo, 1997.

  44. R. J. Zuccherato, The equivalence between elliptic curve and quadratic function field discrete logarithms in characteristic 2, in: Algorithmic Number Theory Symposium ANTS-III, Lecture Notes in Computer Science 1423, Springer-Verlag, 1998, 621-638.
    MathSciNet

Glasnik Matematicki Home Page