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

In 2000 T. Satoh gave the first p-adic point counting algorithm for elliptic curves over finite fields. Satohʹs algorithm was followed by the Satoh–Skjernaa–Taguchi algorithm and furthermore by the arithmetic–geometric mean and modified SST algorithms for characteristic two only. All four algorithms are important to Elliptic Curve Cryptography. 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.