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

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.

• There is probably a better way but say your curve is $E : y^2 = f(x)$. Then $r P = O$ is defined by a polynomial $\psi_r(P)=\psi_r(x,y) = 0$ and $\psi_r(x,y)\psi_r(x,-y) \equiv h_r(x) \bmod y^2-f(x)$. Replace $h_r$ by $\frac{h_r}{\gcd(h_r,h_d)}$ for each $d | r$, its roots should be points of order $r$. – reuns Nov 4 '17 at 12:54
• Oh.. and how about r prime? Maybe there is another way explicit for primes. Well I just need to find to torsion subgroup generator for $E(\mathbb F_{q}$ for $q\in \{ p, p^4 \}$ for two "different" curves. But I would like to know the math behind :) Could you point me to some literature about that, that describe some ways? – Shalec Nov 4 '17 at 16:48
• @reuns How would that turn, if I got two generators of E? In my special case the order of E splits up into 4 factors, 3 small one ($2^2, 3$ if I remember well) and r. Starting from such a generator must be much easier to construct so? – Shalec Nov 12 '17 at 16:54
• @reuns I posted a way, that I derived from some facts, as you can see. It is really basic algebra with low-level elliptic curve theory. (Exept the twisting part, but this is not that hard.) Thanks for your input :) – Shalec Nov 13 '17 at 19:14
• $\langle Q \rangle$ is cyclic of order $\text{ord}(Q)$ but for $k$ large enough and $p \nmid r$, $E(\overline{\mathbb{F}}_{p})[r]=E(\mathbb{F}_{p^k})[r]$ is the product of two cyclic groups of order $r$ (which is seen in the fact $[r]$ is an endomorphism of degree $r^2$ and it is separable for $p \nmid r$, thus its kernel has $r^2$ elements) – reuns Nov 13 '17 at 20:57

# 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.