# Generating random (torsion) point on elliptic curve efficiently

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!

• To generate a point with $[m]P=O$, it might be handy to know the order of the group. – Lord Shark the Unknown Jan 16 at 16:37
• You can select random and encode it by Koblitz's encoding method. In Cryptography that is a problem of mapping messages to points. – kelalaka Jan 16 at 16:39
• @LordSharktheUnknown Well, I am working on supersingular elliptic curves. In that case, the full torsion group $E[m]$ has order $m^2$, while the group generated by $P$ would be of order $m$. Or are you asking about the actual, numerical value of $m$? – Gemeis Jan 16 at 16:41
• Finding the order of $E$ plus two generators shouldn't be much harder than computing the order of a single random point ? – reuns Jan 16 at 18:14
• Torsion points are solutions to division polynomials, so maybe you can solve that instead? For any random $x$ you have $1/2$ chance of a solution $y$. This means on average only two tries. I tested that Tonelli-Shanks using Sage will complete this within tens of microseconds even if $|\mathbb K|$ is around $2^{2000}$, is that fast enough? – Yong Hao Ng Jan 17 at 3:08