A p-adic point counting algorithm for elliptic curves on legendre form

In this paper, we present the general framework for p-adic point counting and we apply it to elliptic curves on Legendre form. We show how the λ-modular polynomial can be used for lifting the curve and Frobenius isogeny to characteristic zero and we show how the associated multiplier gives the action of the lifted Frobenius isogeny on the invariant differential. The result is a point counting algorithm for elliptic curves on Legendre form. The algorithm runs in a time complexity of O(n2μ+1/(μ+1)) for fixed p and a space complexity of O(n2) where pn is the field size. We include results from experimeriments in characteristic p=3,5,…,19.