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

DOI:
https://doi.org/10.1090/S0025-5718-01-01343-6

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 that are larger than those ever reported before.

**[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 ).*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.

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

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

DOI:
https://doi.org/10.1090/S0025-5718-01-01343-6

Received by editor(s):
July 10, 2000

Published electronically:
October 4, 2001

Article copyright:
© Copyright 2001
American Mathematical Society