Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



The parallelized Pollard kangaroo method in real quadratic function fields

Authors: Andreas Stein and Edlyn Teske
Journal: Math. Comp. 71 (2002), 793-814
MSC (2000): Primary 11Y16, 11Y40, 11R29; Secondary 11R58, 14H05
Published electronically: October 4, 2001
MathSciNet review: 1885629
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [Art24] E. Artin. Quadratische Körper im Gebiete der höheren Kongruenzen I, II. Math. Zeitschr., 19:153-206, 1924.
  • [Can87] D. G. Cantor. Computing in the Jacobian of a hyperelliptic curve. Math. Comp., 48:95-101, 1987. MR 88f:11118
  • [GH] 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.
  • [LiD97] LiDIA Group, Technische Universität Darmstadt, Darmstadt, Germany. LiDIA - A library for computational number theory, Version 1.3, 1997.
  • [Pol] J. M. Pollard. Kangaroos, Monopoly and discrete logarithms. J. Cryptology 13:437-447, 2000. CMP 2001:03
  • [Pol78] J. M. Pollard. Monte Carlo methods for index computation (mod $p$). Math. Comp., 32(143):918-924, 1978. MR 58:10684
  • [PR99] S. Paulus and H.-G. Rück. Real and imaginary quadratic representations of hyperelliptic function fields. Math. Comp., 68:1233-1241, 1999. MR 99i:11107
  • [Sha71] D. Shanks. Class number, a theory of factorization and genera. In Proc. Symp. Pure Math. 20, pages 415-440. AMS, Providence, R.I., 1971. MR 47:4932
  • [Sha72] D. Shanks. The infrastructure of a real quadratic field and its applications. In Proc. 1972 Number Th. Conf., Boulder, Col., pages 217-224, 1972. MR 52:10672
  • [SSW96] R. Scheidler, A. Stein, and H. C. Williams. Key-exchange in real quadratic congruence function fields. Des. Codes Cryptogr., 7:153-174, 1996. MR 97d:94009
  • [ST99a] 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.
  • [ST99b] 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).
  • [Ste99] A. Stein. Sharp upper bounds for arithmetics in hyperelliptic function fields. J. Ramanujan Math. Soc., 9-16 (2):1-86, 2001.
  • [Sti93] H. Stichtenoth. Algebraic Function Fields and Codes. Springer, Berlin, 1993. MR 94k:14016
  • [SW98] A. Stein and H. C. Williams. An improved method of computing the regulator of a real quadratic function field. In Algorithmic Number Theory Seminar ANTS-III, volume 1423 of Lecture Notes in Computer Science, pages 607-620. Springer, 1998. MR 2000j:11201
  • [SZ91] 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.
  • [Tes98] E. Teske. Speeding up Pollard's rho method for computing discrete logarithms. In Algorithmic Number Theory Seminar ANTS-III, volume 1423 of Lecture Notes in Computer Science, pages 541-554. Springer, 1998. MR 2000j:11199
  • [Tes00] E. Teske. On random walks for Pollard's rho method. Math. Comp. 70:809-825, 2001. MR 2001g:11194
  • [vOW99] P. C. van Oorschot and M. J. Wiener. Parallel collision search with cryptanalytic applications. J. Cryptology, 12:1-28, 1999. MR 99i:94054
  • [Zim97] H. G. Zimmer et al. Simath manual, 1997. Universität des Saarlandes, Saarbrücken, Germany.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 11Y40, 11R29, 11R58, 14H05

Retrieve articles in all journals with MSC (2000): 11Y16, 11Y40, 11R29, 11R58, 14H05

Additional Information

Andreas Stein
Affiliation: University of Illinois at Urbana-Champaign, Department of Mathematics, 1409 West Green Street, Urbana, Illinois 61801

Edlyn Teske
Affiliation: University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario, Canada N2L 3G1

Received by editor(s): July 10, 2000
Published electronically: October 4, 2001
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society