1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ To generate a point with $[m]P=O$, it might be handy to know the order of the group. $\endgroup$ – Lord Shark the Unknown Jan 16 at 16:37
  • $\begingroup$ You can select random and encode it by Koblitz's encoding method. In Cryptography that is a problem of mapping messages to points. $\endgroup$ – kelalaka Jan 16 at 16:39
  • $\begingroup$ @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$? $\endgroup$ – Gemeis Jan 16 at 16:41
  • $\begingroup$ Finding the order of $E$ plus two generators shouldn't be much harder than computing the order of a single random point ? $\endgroup$ – reuns Jan 16 at 18:14
  • $\begingroup$ 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? $\endgroup$ – Yong Hao Ng Jan 17 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.