Skip to main content

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2021 | OriginalPaper | Buchkapitel

Square Root Time Coleman Integration on Superelliptic Curves

share
TEILEN

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.
Literatur
1.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat Tuitman, Jan. Counting points on curves using a map to P 1. Mathematics of Computation 85.298 (2016): 961–981. MathSciNetCrossRef Tuitman, Jan. Counting points on curves using a map to P 1. Mathematics of Computation 85.298 (2016): 961–981. MathSciNetCrossRef
23.
Zurück zum Zitat 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
Metadaten
Titel
Square Root Time Coleman Integration on Superelliptic Curves
verfasst von
Alex J. Best
Copyright-Jahr
2021
DOI
https://doi.org/10.1007/978-3-030-80914-0_3

Premium Partner