Kedlaya's Algorithm in Larger Characteristic

DOI10.1093/IMRN/RNM095MaRDI QIDQ5439938zbMATH OpenOpenAlexFDO

Authors David I. Harvey

Publication date 30 January 2008

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0610973

zbMATH Keywords

hyperelliptic curvesKedlaya's algorithmlarge characteristicrecurrence relation

Mathematics Subject Classification ID

Curves over finite and local fields (11G20) Computational number theory (11Y99) Applications to coding theory and cryptography of arithmetic geometry (14G50) Computational aspects of algebraic curves (14Q05)

Abstract: We show that the linear dependence on $p$ of the running time of Kedlaya's point-counting algorithm in characteristic $p$ may be reduced to $p^{1/2}$.

Recommendations

• Counting Points in Medium Characteristic Using Kedlaya's Algorithm
• scientific article; zbMATH DE number 2081082
• scientific article; zbMATH DE number 2086894
• Satoh's algorithm in characteristic 2
• An extension of Satoh's algorithm and its implementation

Cited in

(30)

• A cache-friendly truncated FFT
• Computing zeta functions of Kummer curves via multiplicative characters
• Counting points on curves using a map to \(\mathbf P^1\). II.
• Counting points on hyperelliptic curves in average polynomial time
• An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic \(2\)
• Counting points on curves using a map to \(\mathbf{P}^1\)
• A generic approach to searching for Jacobians
• MEMORY EFFICIENT HYPERELLIPTIC CURVE POINT COUNTING
• Report on the Denef-Vercauteren/Kedlaya algorithm
• Sato-Tate distributions
• Computing zeta functions of arithmetic schemes
• Genus 2 point counting over prime fields
• 𝑝-adic point counting on singular superelliptic curves
• Computing zeta functions of generic projective hypersurfaces in larger characteristic
• scientific article; zbMATH DE number 2086894 (Why is no real title available?)
• scientific article; zbMATH DE number 2124950 (Why is no real title available?)
• Explicit Coleman integration for hyperelliptic curves
• Explicit Vologodsky integration for hyperelliptic curves
• scientific article; zbMATH DE number 7656025 (Why is no real title available?)
• Computing zeta functions of cyclic covers in large characteristic
• Explicit Coleman integration in larger characteristic
• Zeta functions of nondegenerate hypersurfaces in toric varieties via controlled reduction in p-adic cohomology
• Computing zeta functions of superelliptic curves in larger characteristic
• An extension of Kedlaya's algorithm for hyperelliptic curves
• Frobenius-stable lattices in rigid cohomology of curves
• Towards computing canonical lifts of ordinary elliptic curves in medium characteristic
• Trustless unknown-order groups
• Counting points on \(C_{ab}\) curves using Monsky-Washnitzer cohomology
• Faster polynomial multiplication via multipoint Kronecker substitution
• Fast arithmetic in unramified \(p\)-adic fields

Describes a project that uses

Uses Software

• NTL
• SageMath

This page was built for publication: Kedlaya's Algorithm in Larger Characteristic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5439938)