On l-th roots and division by l

Abstract

We give a characterization of the codomain $[\ell ]E(k)$ of the multiplication-by-$\ell$ map $[\ell ]$ in the case of elliptic curves over a field $k$ of characteristic $\ne 2,3$ with $\ell$-torsion $E[\ell ]=⟨W_1,W_2⟩$ fully defined over $k$, for primes $\ell$ different from the characteristic. We show that a point $Q\in E(k)$ lies in $[\ell ]E(k)$ if and only if $h_{W_1}(-Q)$ and $h_{W_2}(-Q)$ are $\ell$-powers of $k$, where $h_{W_1}$ and $h_{W_2}$ are functions on $E$ with divisor $\mathrm{div}(h_{W_i})=\ell W_i-\ell P_{\infty }$. Our characterization leads to an effective procedure to find pre-images of $[\ell ]$ by solving an order $\ell$ system of linear equations and computing a polynomial gcd.

18 pages no figures