0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – reuns Nov 4 '17 at 12:54
  • $\begingroup$ 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? $\endgroup$ – Shalec Nov 4 '17 at 16:48
  • $\begingroup$ @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? $\endgroup$ – Shalec Nov 12 '17 at 16:54
  • $\begingroup$ @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 :) $\endgroup$ – Shalec Nov 13 '17 at 19:14
  • 1
    $\begingroup$ $\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) $\endgroup$ – reuns Nov 13 '17 at 20:57
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.