Skip to main content
edited body
Source Link

Let $E$ be an elliptic curve over a finite field $\mathbb{F}_q$$\mathbb{F}_p$ of characteristic $p$. Let $P,Q\in E(\mathbb{F}_q)$, such that $Q=mP+n\tau(P)$, where $\tau$ is the p-th power of frobenious map and $m$ and $n$ are integers. It is clear that the problem of finding $m$ and $n$ from $Q$ and $P$ must be at least as hard as the discrete logarithm problem. I am looking for some algorithm which can solve this kind of problems. Is there an algorithm for general cases, for example when we have three points $Q,P_1,P_2\in E(\mathbb{F}_q)$ such that $Q=mP_1+nP_2$ (number of points can be more than 3).

Let $E$ be an elliptic curve over a finite field $\mathbb{F}_q$ of characteristic $p$. Let $P,Q\in E(\mathbb{F}_q)$, such that $Q=mP+n\tau(P)$, where $\tau$ is the p-th power of frobenious map and $m$ and $n$ are integers. It is clear that the problem of finding $m$ and $n$ from $Q$ and $P$ must be at least as hard as the discrete logarithm problem. I am looking for some algorithm which can solve this kind of problems. Is there an algorithm for general cases, for example when we have three points $Q,P_1,P_2\in E(\mathbb{F}_q)$ such that $Q=mP_1+nP_2$ (number of points can be more than 3).

Let $E$ be an elliptic curve over a finite field $\mathbb{F}_p$ of characteristic $p$. Let $P,Q\in E(\mathbb{F}_q)$, such that $Q=mP+n\tau(P)$, where $\tau$ is the p-th power of frobenious map and $m$ and $n$ are integers. It is clear that the problem of finding $m$ and $n$ from $Q$ and $P$ must be at least as hard as the discrete logarithm problem. I am looking for some algorithm which can solve this kind of problems. Is there an algorithm for general cases, for example when we have three points $Q,P_1,P_2\in E(\mathbb{F}_q)$ such that $Q=mP_1+nP_2$ (number of points can be more than 3).

Source Link

Is there an algorithm to find a linear dependence between points on elliptic curves?

Let $E$ be an elliptic curve over a finite field $\mathbb{F}_q$ of characteristic $p$. Let $P,Q\in E(\mathbb{F}_q)$, such that $Q=mP+n\tau(P)$, where $\tau$ is the p-th power of frobenious map and $m$ and $n$ are integers. It is clear that the problem of finding $m$ and $n$ from $Q$ and $P$ must be at least as hard as the discrete logarithm problem. I am looking for some algorithm which can solve this kind of problems. Is there an algorithm for general cases, for example when we have three points $Q,P_1,P_2\in E(\mathbb{F}_q)$ such that $Q=mP_1+nP_2$ (number of points can be more than 3).