Skip to main content
main-content
Top

Hint

Swipe to navigate through the chapters of this book

2021 | OriginalPaper | Chapter

Square Root Time Coleman Integration on Superelliptic Curves

share
SHARE

Abstract

Since Kedlaya first introduced a p-adic algorithm for computing zeta functions of hyperelliptic curves, many related algorithms for computing both zeta functions and Coleman integrals on various classes of algebraic curves have been studied. These algorithms compute in the Monsky-Washnitzer cohomology or the rigid cohomology of the curve to determine the action of Frobenius on this cohomology.
We give a new algorithm for explicitly computing Coleman integrals on superelliptic curves over unramified extensions of p-adic fields. The runtime is softly linear with respect to the square root of the size of the residue field, bringing the runtime in line with that of the corresponding zeta function algorithms. We also describe the implementation of this algorithm in Nemo, a new package for the Julia programming language, which adds functionality for computational number theory. We compare Nemo with other systems in use in this area.
Literature
1.
go back to reference Balakrishnan, Jennifer S., Robert W. Bradshaw, and Kiran S. Kedlaya. Explicit Coleman Integration for Hyperelliptic Curves. In ANTS-IX 2010, LNCS 6197, pp. 16–31, 2010. Balakrishnan, Jennifer S., Robert W. Bradshaw, and Kiran S. Kedlaya. Explicit Coleman Integration for Hyperelliptic Curves. In ANTS-IX 2010, LNCS 6197, pp. 16–31, 2010.
2.
go back to reference Balakrishnan, Jennifer S. Coleman integration for even-degree models of hyperelliptic curves. LMS Journal of Computation and Mathematics 18.1 (2015): 258–265. MathSciNetCrossRef Balakrishnan, Jennifer S. Coleman integration for even-degree models of hyperelliptic curves. LMS Journal of Computation and Mathematics 18.1 (2015): 258–265. MathSciNetCrossRef
4.
go back to reference Balakrishnan Jennifer S., and Jan Tuitman. Explicit Coleman integration for curves. arXiv preprint arXiv:1710.01673. 2020 Jan 13. Balakrishnan Jennifer S., and Jan Tuitman. Explicit Coleman integration for curves. arXiv preprint arXiv:1710.01673. 2020 Jan 13.
5.
go back to reference Besser, Amnon. Heidelberg lectures on Coleman integration. In The Arithmetic of Fundamental Groups, pp. 3–52. Springer, Berlin, Heidelberg, 2012. Besser, Amnon. Heidelberg lectures on Coleman integration. In The Arithmetic of Fundamental Groups, pp. 3–52. Springer, Berlin, Heidelberg, 2012.
6.
go back to reference Besser, Amnon, and Rob De Jeu. Li (p)- Service? An Algorithm for Computing p-Adic Polylogarithms. Mathematics of Computation 77, no. 262 (2008): 1105–34. Besser, Amnon, and Rob De Jeu. Li (p)- Service? An Algorithm for Computing p-Adic Polylogarithms. Mathematics of Computation 77, no. 262 (2008): 1105–34.
7.
go back to reference Best, Alex J. Explicit Coleman integration in larger characteristic. Proceedings of the Thirteenth Algorithmic Number Theory Symposium, The Open Book Series, 2(1), 85–102, 2019. MathSciNet Best, Alex J. Explicit Coleman integration in larger characteristic. Proceedings of the Thirteenth Algorithmic Number Theory Symposium, The Open Book Series, 2(1), 85–102, 2019. MathSciNet
10.
go back to reference Bosma, Wieb, John Cannon, and Catherine Playoust. The Magma algebra system. I. The user language, J. Symbolic Comput., 24 (1997), 235–265. MathSciNetCrossRef Bosma, Wieb, John Cannon, and Catherine Playoust. The Magma algebra system. I. The user language, J. Symbolic Comput., 24 (1997), 235–265. MathSciNetCrossRef
13.
go back to reference Gaudry, Pierrick, and Nicolas Gürel. An extension of Kedlaya’s point-counting algorithm to superelliptic curves. Advances in Cryptology - ASIACRYPT 2001, Springer, Berlin, Heidelberg, 2001. Gaudry, Pierrick, and Nicolas Gürel. An extension of Kedlaya’s point-counting algorithm to superelliptic curves. Advances in Cryptology - ASIACRYPT 2001, Springer, Berlin, Heidelberg, 2001.
14.
go back to reference Gonçalves, Cécile. A point counting algorithm for cyclic covers of the projective line. Contemporary mathematics 637 (2015): 145. Gonçalves, Cécile. A point counting algorithm for cyclic covers of the projective line. Contemporary mathematics 637 (2015): 145.
15.
go back to reference Harvey, David. Counting points on hyperelliptic curves in average polynomial time. Annals of Mathematics 179, no. 2 (2014): 783–803. MathSciNetCrossRef Harvey, David. Counting points on hyperelliptic curves in average polynomial time. Annals of Mathematics 179, no. 2 (2014): 783–803. MathSciNetCrossRef
16.
go back to reference Harvey, David. Kedlaya’s Algorithm in Larger Characteristic. IMRN: International Mathematics Research Notices 2007 (2007). Harvey, David. Kedlaya’s Algorithm in Larger Characteristic. IMRN: International Mathematics Research Notices 2007 (2007).
17.
go back to reference Hashimoto, Sachi, and Travis Morrison. Chabauty-Coleman Computations on Rank 1 Picard Curves, preprint. Hashimoto, Sachi, and Travis Morrison. Chabauty-Coleman Computations on Rank 1 Picard Curves, preprint.
18.
go back to reference Kedlaya, Kiran S. Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, J. Ramanujan Math. Soc. 16 (2001), no. 4, 323–338; errata, ibid. 18 (2003), 417–418. Kedlaya, Kiran S. Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, J. Ramanujan Math. Soc. 16 (2001), no. 4, 323–338; errata, ibid. 18 (2003), 417–418.
19.
go back to reference McCallum, William, and Bjorn Poonen. The Method of Chabauty and Coleman. Explicit Methods in Number Theory 36 (2012): 99–117. MathSciNetMATH McCallum, William, and Bjorn Poonen. The Method of Chabauty and Coleman. Explicit Methods in Number Theory 36 (2012): 99–117. MathSciNetMATH
20.
go back to reference Minzlaff, Moritz. Computing zeta functions of superelliptic curves in larger characteristic. Mathematics in Computer Science 3.2 (2010): 209–224. MathSciNetCrossRef Minzlaff, Moritz. Computing zeta functions of superelliptic curves in larger characteristic. Mathematics in Computer Science 3.2 (2010): 209–224. MathSciNetCrossRef
21.
go back to reference Towse, Christopher. Weierstrass Points on Cyclic Covers of the Projective Line. Transactions of the American Mathematical Society 348, no. 8 (1996): 3355–3378. MathSciNetCrossRef Towse, Christopher. Weierstrass Points on Cyclic Covers of the Projective Line. Transactions of the American Mathematical Society 348, no. 8 (1996): 3355–3378. MathSciNetCrossRef
22.
23.
go back to reference Tuitman, Jan. Counting points on curves using a map to P 1, II. Finite Fields and Their Applications 45 (2017): 301–322. MathSciNetCrossRef Tuitman, Jan. Counting points on curves using a map to P 1, II. Finite Fields and Their Applications 45 (2017): 301–322. MathSciNetCrossRef
Metadata
Title
Square Root Time Coleman Integration on Superelliptic Curves
Author
Alex J. Best
Copyright Year
2021
DOI
https://doi.org/10.1007/978-3-030-80914-0_3

Premium Partner