How to show there exists no solution to a discrete logarithm problem on an Elliptic Curve?

486 Views Asked by At

The exact problem is to show that $\nexists$k such that $k(1,2) = (4,5)$ on the elliptic curve defined by $\widetilde{E}: y^2 = x^3 -14x + 17$ over $\mathbb Q$.

Background: E: $y^2 = x^3 + 3$ over $F_7$. On E we have 4(1,2) = (4,5). Now the points P = (1,2) and Q = (4,5) are on both E and $\widetilde{E}$ and $\widetilde{E}$ was found by uplifting E (from mod 7 to Q). Also it was discovered that 2(1,2) = (1,-2) and 3(1,2) = $\infty $ mod 73 on $\widetilde{E}$.

2

There are 2 best solutions below

3
On BEST ANSWER

You have found that modulo $73$, $(1,2)$ is a point of order $3$.
Since $(4,5)$ modulo $73$ is neither $(1,2),(1,-2)$ nor $\infty$, it can't be in the group generated by $(1,2)$.

You should try to compute the group of the curve reduced modulo a few primes and find primes other than $73$ where the reduction of $(4,5)$ is not in the subgroup generated by the reduction of $(1,2)$.

0
On

Alternatively you can use canonical heights on $E$. By the properties of canonical heights $\hat{h}(kQ)=k^2\cdot \hat{h}(Q)$, for any $Q\in E(\mathbb{Q})$ and any $k\geq 1$. Thus, if $k\cdot (1,2) = (4,5)$, it follows that $k^2\cdot \hat{h}(1,2)=\hat{h}(4,5)$, but $$\hat{h}(1,2)= 1.14638174824\ldots, \text{ and } \hat{h}(4,5)=1.15045975869,$$ so $k^2\cdot \hat{h}(1,2)=\hat{h}(4,5)$ is impossible for $k\in\mathbb{N}$.

Using heights you can do a little better, and check that there are no $n$ and $m$ integers such that $n\cdot (1,2)=m\cdot (4,5)$. Any such $\mathbb{Z}$-linear relation would be picked up by the height matrix of $(1,2)$ and $(4,5)$. More concretely, if $P$ and $Q$ are rational points, we define $\langle P,Q\rangle = \hat{h}(P+Q)-\hat{h}(P)-\hat{h}(Q)$ and a matrix $$H=\left(\begin{array}{cc} \langle P,P\rangle & \langle P,Q\rangle \\ \langle Q,P\rangle & \langle Q,Q\rangle \end{array} \right),$$ and there is a $\mathbb{Z}$-linear combination of $P$ and $Q$ (modulo torsion) if and only if the determinant of $H$ is zero. However, for $P=(1,2)$ and $Q=(4,5)$ the determinant of $H$ is $1.15092709663\ldots \neq 0$, and therefore $P$ and $Q$ are independent.