Let $E$ be a supersingular elliptic curve which is defined over $\mathbb{F}_q$ and $P\in E$. Then there exist a distortion map with respect to $P$. I am looking for an algorithm which finds the map and the complexity of the algorithm.

The paper "Easy Decision-Diffie-Hellman Groups" by S. Galbraith and V. Rotger contains such an algorithm, which requires a polynomial number of operations.