  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.
