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,m1]$ 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 $$RaP=bQ$$ where $a\in [0,m1]$. 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.
1 Answer
$\begingroup$
$\endgroup$
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.

$\begingroup$ 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. $\endgroup$– DDTCommented Jun 18, 2019 at 21:14