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

Question

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.

Answer 1

There's probably an even quicker way, but here's one idea. Compute the Weil pairings $<P,Q>$ and $<R,Q>=<P,Q>^a$ and $<P,R>=<P,Q>^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.