I am looking for an efficient way to generate a random point on an elliptic curve over a finite field, $E(\mathbb{K})$.
I know that you can pick a random $x$, compute e.g. in Weierstrass coordinates $f=x^3+ax+b$, check if it is a quadratic residue and then solve $y^2=f$ using the Tonelli-Shanks or Cipolla algorithm. The former roughly has a complexity of $O(\log^2_2|\mathbb{K}|)$ multiplications on $\mathbb{K}$, while the latter only conditionally runs faster. If your finite field is huge and your computational power weak, this can be a lot. Is there a way to do this faster?
Furthermore, what if I want the point to belong to a particular torsion group, e.g. let's say I want to generate a point $P$ with $[m]P=O$? Is there a shortcut for such points, or do I have to generate them, and then test?
EDIT: In more detail, I am working with supersingular elliptic curves over finite field of characteristic $p=2^u3^v\pm1$, such that $p$ prime. It roughly holds that $2^u\approx3^v$ such that there are two very large coprime torsion groups $E[2^u]$ and $E[3^v]$. The points I want to generate are in either of these torsion groups.
Thank you for any help!