# Expressing a torsion point of an elliptic curve as a combination of the generators

I'm facing the following problem: Suppose that we have a finite field $$\mathbb{F}_p$$ and an elliptic curve $$E$$ defined over it. Suppose that for $$m\in \mathbb{Z}$$ not multiple of the characteristic of the base field. So we have an isomorphism $$E[m]\longleftrightarrow (\mathbb{Z}/m\mathbb{Z})^2$$ Suppose we know that $$E[m]\subset E(\mathbb{F}_q)$$ where $$q$$ is a power of $$p$$. Suppose also that we have given generators $$P,Q\in E[m]$$ and a third point $$R\in E[m]$$. I want to find $$a,b \in [0,m-1]$$ for which $$R=aP+bQ$$ What is the computational cost of this problem? The most efficient algorithm i'm thinking about consists of trying to solve a lot of ECDLP $$R-aP=bQ$$ where $$a\in [0,m-1]$$. This of course has a computational cost $$O(m\sqrt{m})$$ since for the single ECDLP there are algorithm with computational cost $$O(\sqrt{m})$$. Thanks to all for your time.

There's probably an even quicker way, but here's one idea. Compute the Weil pairings $$$$ and $$=^a$$ and $$=^b$$. Then you just have to solve the DLP twice in $$\mathbb F_q^*$$ to find $$a$$ and $$b$$, and there are subexponential algorithms for DLP over finite fields. And the Weil pairing is polynomial (essentially linear) time.
• Thank you for your answer and your time. This is very effective way to compute it. Now i have another curiosity: if the 2 points are not known to be the generators of a torsion subgroup, are there effective algorithms solving the "double discrete logarithm" problem: $$R=aP+bQ$$ Thanks again. Jun 18 '19 at 21:14