How to find a generator of a torsion subgroup of an elliptic curve with specific order?

Question

Let $E(\mathbb F_q)$ bei any elliptic curve over a finite field with characteristic > 3. Is there any mathematical way, or even algorithm, to find a r-torsion subgroup or a generator of, when r is given?

Definition: $E(\mathbb F_q)[r]=\{P\in E: rP = \mathcal O\}$

First Steps in Sagemath to find such a torsion subgroup

Generation of the group

u = 2^35 - 2^32 -2^18 + 2^8 +1
p=1/980*(u^10 + 2*u^9 + 5*u^8 + 48*u^6 + 152*u^5 + 240* u^4 + 625*u^2 + 2398*u + 3125)
r = u^8 + 48*u^4 + 625
R = GF(p)
_.<s> = PolynomialRing(R)
R4.<s> = R.extension(s^4 - 2, 's')
E = EllipticCurve(R4, [s,0]) ; E

And the loop for finding that element:

P = E.random_element()
while r*P != O:
    P = E.random_element()

ends up in infinity time consumption.

Answer 1

The Case of an elliptic curve over a finite field with prime order

Lets consider $\newcommand\F[1]{\mathbb F_{p^{#1}}}K=\F{}$ for a prime $p$ and $E(K):\ y^2= x^3+Ax+B$ be an elliptic curve in general Weierstraß equation for $char(p)>3$. If we choose E to be a pairing-friendly curve, we can reduce that curve to a fitting model and receive on that way a nice parameterization of the prime $p$, torsion subgroup order $r$ and the trace of Frobenius $t$.

The connection through $\# E$ and $t$ is given as: $\# E = q+1-t$, where $q=p$ in our case, instead of $q=p^n$. That means, we are able to compute the order of E. Since the $r$-torsion subgroup is a subgroup of $E$, we get: $r\mid \# E$. Let $n:=\# E/r$.

Now pick a generator of E (probably not with order $n$) (maybe it will work with any point instead, but I wouldn't bet on this.) and multiply it with $n$. Since any Point will fullfil $\#E \cdot P = (0:1:0) = r\cdot n\cdot P$. If $r$ is prime (which will in that case) we have found a generator of $E(K)[r]$.

The Case of an elliptic curve over a finite field with prime-power order

Let $K:=\F{k}$ for any integer $k>1$. Since we know the order of $E(\F{})$, we are able to compute the order of $E(K)$.

Break: Computing that order

Let $x^2-tx+q=(x-\alpha)(x-\beta)$. Then we have $$\mathbb Z\ni s_n:= \alpha^n +\beta^n$$ beginning with $s_0=2, s_1=a$ and $s_{n+1}=ts_n - qs_{n-1}$ and $$\#E(\F{k})=q^k +1 - (\alpha^k +\beta^k)$$ (I guess the proof shall be found in Washington's "Elliptic Curves: Number Theory and Cryptography, Second Edition".

Continue

Since we are looking for the r-torsion subgroup again, we may divide $\# E(K)/r =:n$ and take a generator of E, do same as before. Now we have a Point $Q$ on $E$ that has prime order $r$. The funny thing is to get that point onto another curve $E'(\F{k/m})$, where $m\in\{2,3,4,6\}$. In my special purpose, $E'$ is a twist of $E(\F k)$. Therefore, there is an isomorphism $\psi:\ E\to E'$ which can be explicit defined. Using that twist, maps the point $E\ni Q \mapsto Q'\in E'$, but only over $\F k$.

There is one problem, that could occur: The $r$ do not has to divide the order. But this can be solved if you lift $P\in E(\F{})$ to $E(\F{16})$

This is my self derived strategy, so if anyone has a simplier or better way, tell me. I would be happy to learn more about that.

Finding generators of $E$

Well, the chosen point does not has to be a generator at all. Just take any point that does not map to $(0:1:0)$, if it is multiplied by $n$. The resulting point has prime order $r$, thanks to lagranges theorem. Therefore, that point is a generator of a cyclic subgroup: the r-torsion subgroup. Now one could take a look onto all points of that subgroup and pick the "best" representation.