The parallelized Pollard kangaroo method in real quadratic function fields
HTML articles powered by AMS MathViewer
- by Andreas Stein and Edlyn Teske PDF
- Math. Comp. 71 (2002), 793-814 Request permission
Abstract:
We show how to use the parallelized kangaroo method for computing invariants in real quadratic function fields. Specifically, we show how to apply the kangaroo method to the infrastructure in these fields. We also show how to speed up the computation by using heuristics on the distribution of the divisor class number, and by using the relatively inexpensive baby steps in the real quadratic model of a hyperelliptic function field. Furthermore, we provide examples for regulators and class numbers of hyperelliptic function fields of genus $3$ that are larger than those ever reported before.References
- E. Artin. Quadratische Körper im Gebiete der höheren Kongruenzen I, II. Math. Zeitschr., 19:153–206, 1924.
- David G. Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp. 48 (1987), no. 177, 95–101. MR 866101, DOI 10.1090/S0025-5718-1987-0866101-0
- P. Gaudry and R. Harley. Counting points on hyperelliptic curves over finite fields. In Algorithmic Number Theory Seminar ANTS-IV, volume 1838 of Lecture Notes in Computer Science, pages 313–332. Springer, 2000.
- LiDIA Group, Technische Universität Darmstadt, Darmstadt, Germany. LiDIA - A library for computational number theory, Version 1.3, 1997.
- J. M. Pollard. Kangaroos, Monopoly and discrete logarithms. J. Cryptology 13:437–447, 2000.
- J. M. Pollard, Monte Carlo methods for index computation $(\textrm {mod}\ p)$, Math. Comp. 32 (1978), no. 143, 918–924. MR 491431, DOI 10.1090/S0025-5718-1978-0491431-9
- Sachar Paulus and Hans-Georg Rück, Real and imaginary quadratic representations of hyperelliptic function fields, Math. Comp. 68 (1999), no. 227, 1233–1241. MR 1627817, DOI 10.1090/S0025-5718-99-01066-2
- Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385
- Daniel Shanks, The infrastructure of a real quadratic field and its applications, Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972) Univ. Colorado, Boulder, Colo., 1972, pp. 217–224. MR 0389842
- R. Scheidler, A. Stein, and Hugh C. Williams, Key-exchange in real quadratic congruence function fields, Des. Codes Cryptogr. 7 (1996), no. 1-2, 153–174. Special issue dedicated to Gustavus J. Simmons. MR 1377761, DOI 10.1007/BF00125081
- A. Stein and E. Teske. Catching kangaroos in function fields. Technical Report CORR 99-09, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, 1999. 19 pages.
- A. Stein and E. Teske. Explicit bounds and heuristics on class numbers in hyperelliptic function fields. Math. Comp., posted on October 4, 2001, PII S0025-5718(01)01385-0 (to appear in print).
- A. Stein. Sharp upper bounds for arithmetics in hyperelliptic function fields. J. Ramanujan Math. Soc., 9–16 (2):1–86, 2001.
- Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. MR 1251961
- Andreas Stein and Hugh C. Williams, An improved method of computing the regulator of a real quadratic function field, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 607–620. MR 1726105, DOI 10.1007/BFb0054896
- 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.
- Edlyn Teske, Speeding up Pollard’s rho method for computing discrete logarithms, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 541–554. MR 1726100, DOI 10.1007/BFb0054891
- Edlyn Teske, On random walks for Pollard’s rho method, Math. Comp. 70 (2001), no. 234, 809–825. MR 1697652, DOI 10.1090/S0025-5718-00-01213-8
- Paul C. van Oorschot and Michael J. Wiener, Parallel collision search with cryptanalytic applications, J. Cryptology 12 (1999), no. 1, 1–28. MR 1664774, DOI 10.1007/PL00003816
- H. G. Zimmer et al. Simath manual, 1997. Universität des Saarlandes, Saarbrücken, Germany.
Additional Information
- Andreas Stein
- Affiliation: University of Illinois at Urbana-Champaign, Department of Mathematics, 1409 West Green Street, Urbana, Illinois 61801
- Email: andreas@math.uiuc.edu
- Edlyn Teske
- Affiliation: University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario, Canada N2L 3G1
- Email: eteske@cacr.math.uwaterloo.ca
- Received by editor(s): July 10, 2000
- Published electronically: October 4, 2001
- © Copyright 2001 American Mathematical Society
- Journal: Math. Comp. 71 (2002), 793-814
- MSC (2000): Primary 11Y16, 11Y40, 11R29; Secondary 11R58, 14H05
- DOI: https://doi.org/10.1090/S0025-5718-01-01343-6
- MathSciNet review: 1885629