Mathematics of Computation

Author(s): P. Gaudry; E. Thomé; N. Thériault; C. Diem.
Journal: Math. Comp. 76 (2007), 475-492.
MSC (2000): Primary 11Y16; Secondary 11T71, 94A60
Posted: October 4, 2006
Retrieve article in: PDF DVI PostScript

Abstract: In this article, we examine how the index calculus approach for computing discrete logarithms in small genus hyperelliptic curves can be improved by introducing a double large prime variation. Two algorithms are presented. The first algorithm is a rather natural adaptation of the double large prime variation to the intended context. On heuristic and experimental grounds, it seems to perform quite well but lacks a complete and precise analysis. Our second algorithm is a considerably simplified variant, which can be analyzed easily. The resulting complexity improves on the fastest known algorithms. Computer experiments show that for hyperelliptic curves of genus three, our first algorithm surpasses Pollard's Rho method even for rather small field sizes.

1.: L. M. Adleman, J. DeMarrais, and M.-D. Huang, A subexponential algorithm for discrete logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves over finite fields, ANTS-I (L. Adleman and M.-D. Huang, eds.), Lecture Notes in Comput. Sci., vol. 877, Springer-Verlag, 1994, pp. 28-40. MR 1322708 (96b:11078)
2.: A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, MA, 1974. MR 0413592 (54:1706)
3.: D. G. Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp. 48 (1987), no. 177, 95-101. MR 0866101 (88f:11118)
4.: F. Chung and L. Lu, The diameter of sparse random graphs, Adv. in Appl. Math. 26 (2001), 257-279. MR 1826308 (2002c:05138)
5.: D. Coppersmith, Solving linear equations over $\mathrm{GF}(2)$ via block Wiedemann algorithm, Math. Comp. 62 (1994), no. 205, 333-350. MR 1192970 (94c:11124)
6.: J.-M. Couveignes, Algebraic groups and discrete logarithm, Public-key cryptography and computational number theory, de Gruyter, 2001, pp. 17-27. MR 1881624 (2003a:11160)
7.: C. Diem, Index calculus algorithm for plane curves of small degree, ANTS-VII (F. Heß, S. Pauli and M. Pohst, eds.), Lecture Notes in Comput. Sci., vol. 4076, Springer-Verlag, 2006, pp. 543-557.
8.: A. Enge, Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time, Math. Comp. 71 (2002), 729-742.MR 1885624 (2003b:68083)
9.: A. Enge and P. Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arith. 102 (2002), 83-103. MR 1884958 (2002k:11225)
10.: P. Flajolet, D. Knuth, and B. Pittel, The first cycles in an evolving graph, Discrete Math. 75 (1989), 167-215. MR 1001395 (90d:05184)
11.: P. Gaudry, An algorithm for solving the discrete log problem on hyperelliptic curves, Advances in Cryptology, EUROCRYPT 2000 (B. Preneel, ed.), Lecture Notes in Comput. Sci., vol. 1807, Springer-Verlag, 2000, Proc. International Conference on the Theory and Application of Cryptographic Techniques, Brugge, Belgium, May 2000, Proceedings, pp. 19-34.MR 1772021
12.: -, Index calculus for abelian varieties and the elliptic curve discrete logarithm problem, Cryptology ePrint Archive: Report 2004/073, 2004.
13.: F. Heß, Computing Riemann-Roch spaces in algebraic function fields and related topics, J. Symbolic Comput. 33 (2002), 425-445. MR 1890579 (2003j:14032)
14.: -, Computing relations in divisor class groups of algebraic curves over finite fields, Preprint, 2004.
15.: M.-D. Huang and D. Ierardi, Counting points on curves over finite fields, J. Symbolic Comput. 25 (1998), 1-21. MR 1600606 (98i:11040)
16.: N. Koblitz, Hyperelliptic cryptosystems, J. of Cryptology 1 (1989), 139-150.MR 1007215 (90k:11165)
17.: A. K. Lenstra and M. S. Manasse, Factoring with two large primes, Math. Comp. 63 (1994), no. 208, 785-798. MR 1250773 (95a:11107)
18.: P. Leyland, A. K. Lenstra, B. Dodson, A. Muffett, and S. S. Wagstaff, Jr., MPQS with three large primes, ANTS-V (C. Fieker and D. R. Kohel, eds.), Lecture Notes in Comput. Sci., vol. 2369, Springer-Verlag, 2002, 5th Algorithmic Number Theory Symposium, Sydney, Australia, July 2002, Proceedings, pp. 448-462. MR 2041103 (2005d:11178)
19.: A. Menezes, Y.-H. Wu, and R. Zuccherato, An elementary introduction to hyperelliptic curves, Appendix to Algebraic aspects of cryptography, by N. Koblitz, pages 155-178, Springer-Verlag, 1998. MR 1610535 (2000a:94012)
20.: V. Müller, A. Stein, and C. Thiel, Computing discrete logarithms in real quadratic congruence function fields of large genus, Math. Comp. 68 (1999), no. 226, 807-822. MR 1620235 (99i:11119)
21.: J. Pila, Frobenius maps of abelian varieties and finding roots of unity in finite fields, Math. Comp. 55 (1990), no. 192, 745-763. MR 1035941 (91a:11071)
22.: S. Pohlig and M. Hellman, An improved algorithm for computing logarithms over $\mathrm{GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory IT-24 (1978), 106-110. MR 0484737 (58:4617)
23.: N. Thériault, Index calculus attack for hyperelliptic curves of small genus, Advances in Cryptology, ASIACRYPT 2003 (C. Laih, ed.), Lecture Notes in Comput. Sci., vol. 2894, Springer-Verlag, 2003, Proc. 9th International Conference on the Theory and Applications of Cryptology and Information Security, Nov. 30, Dec. 4, 2003, Taipei, Taiwan, Proceedings, pp. 75-92.MR 2093253 (2006d:94068)
24.: E. Thomé, Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, J. Symbolic Comput. 33 (2002), no. 5, 757-775.MR 1919913 (2004b:11172)
25.: -, Algorithmes de calcul de logarithme discret dans les corps finis, Thèse, École polytechnique, May, 2003.
26.: E. Volcheck, Computing in the Jacobian of a plane algebraic curve, ANTS-I (L. Adleman and M.-D. Huang, eds.), Lecture Notes in Comput. Sci., vol. 877, Springer-Verlag, 1994, pp. 221-233.MR 1322725 (96a:14033)
27.: T. Wollinger, J. Pelzl, and C. Paar, Cantor versus Harley: Optimization and analysis of explicit formulae for hyperelliptic curve cryptosystem, Tech. report, Universität Bochum, 2004, Available at http://www.crypto.rub.de/.

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 11T71, 94A60

P. Gaudry
Affiliation: École polytechnique, LIX, 91128 Palaiseau Cedex, France

E. Thomé
Affiliation: INRIA Lorraine, SPACES, 615 rue du Jardin botanique, 54602 Villers-Lès-Nancy Cedex, France

N. Thériault
Affiliation: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, N2L 3G1 Canada

C. Diem
Affiliation: Faculty for Mathematics and Informatics, University of Leipzig, Augustusplatz 10-11, 04109 Leipzig, Germany

DOI: 10.1090/S0025-5718-06-01900-4
PII: S 0025-5718(06)01900-4
Received by editor(s): February 16, 2005
Received by editor(s) in revised form: November 21. 2005
Posted: October 4, 2006
Copyright of article: Copyright 2006, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS