In this question, I asked for the explicit description of the map $\phi_\alpha\in \operatorname{End}(E)$ corresponding to $\alpha\in \mathcal{O}_K$ for an elliptic curve $E/F$ with CM by $\mathcal{O}_K$.
Reuns gave an answer:
On the elliptic curve side $\alpha^{-1}L/L$ becomes an order $m=|\alpha|^2$ subgroup $H\subset E[m]$, and $(\wp_L(\alpha z),\wp_L'(\alpha z))$ becomes $$(x(\phi_\alpha),y(\phi_{\alpha}))= (C+ \alpha^{-2} \sum_{h\in H} x(.+h), \alpha^{-3} \sum_{h\in H} y(.+h))\tag{1}$$ where $C= -\alpha^{-2}\sum_{h\in H-O} x(h)$. Note that the RHS are rational functions in $x,y$, $g_2(L),g_3(L)$ and the coordinates of elements of $H$.At first we don't know $H$, so try each order $m$ subgroup of $E[m]$ and find if $(1)$ is an endomorphism, ie. if $y(\phi_\alpha)^2=4x(\phi_\alpha)^3-g_2(L)x(\phi_\alpha)-g_3(L)$.
Question: In practice, how would one most efficiently compute $\phi_\alpha(P)$ on $E(\mathbb{F}_q)$ ($P$ an $\mathbb{F}_q$-rational point)? Can it be done in (heuristic?) polynomial time w.r.t the digits of $q$ (for a fixed CM curve)? What is our fastest method in practice; does it use Reuns' answer?
Notes: It seems to me that we can start as follows: $\alpha=a+b\sqrt{-d}$ (let's assume $a,b$ are integers for brevity -- that is that $d\equiv 2,3\mod 4$), then $\phi_\alpha=(\phi_a+\phi_b(\phi_{\sqrt{-d}}))\in \operatorname{End}(E)$, and we only need to compute $\phi_{\sqrt{-d}}(P)$ (the map corresponding to $\sqrt{-d}$) efficiently.