Computing Canonical Heights on Elliptic Curves in Quasi-Linear Time

Abstract

We introduce an algorithm that can be used to compute the canonical height of a point on an elliptic curve over the rationals in quasi-linear time. As in most previous algorithms, we decompose the difference between the canonical and the naive height into an archimedean and a non-archimedean term. Our main contribution is an algorithm for the computation of the non-archimedean term that requires no integer factorization and runs in quasi-linear time.

15 pages. v2: Fixed an inaccuracy in Algorithm 6.1 pointed out by E. Wells. Minor changes in Sections 4 and 6. Updated timings

Cited by in corpus (5)

• Canonical Heights on Genus Two Jacobians
• Computing Unit Groups of Curves
• Explicit arithmetic intersection theory and computation of Néron-Tate heights
• Archimedean local height differences on elliptic curves
• Computing the Canonical Height of a Point in Projective Space