0
$\begingroup$

I have an elliptic curve $E$ over $\mathbb{F}_{7}$ defined by $y^2=x^3+2$ with the point at infinity $\mathcal{O}$

I am given the point $(3,6)$ and need to find the line which intersects with $E$ at only this point

I am told that this line is $y\equiv (4x+1)\mod 7$

I have verified that this is the case, however my question is, how would I go about finding that equation in the first place?


What I'm asking for is a method, which would take in the elliptic curve $E$ and a point on the curve $P$ and output the line which intersects with $E$ at only this point

In the example above, we would have the following

\begin{align}\text{input} &= \begin{cases}y^2=x^3 + 2\\ P=(3,6)\end{cases}\\ \text{output} &= y\equiv (4x+1)\mod 7\end{align}

$\endgroup$
  • $\begingroup$ The line will intersect $E$ at $\mathcal O$, too. Do you know how to treat this problem for an elliptic curve over $\Bbb R$ or $\Bbb C$ instead? $\endgroup$ – Travis Willse Mar 6 '17 at 12:38
  • $\begingroup$ No, I'm teaching myself about Elliptic Curves, as a part of an encryption system so have only learnt about it in a finite field $\endgroup$ – lioness99a Mar 6 '17 at 12:43
1
$\begingroup$

An idea:

A general line through $\;(3,6)\;$ is of the form $\;y-6=m(x-3)\implies \color{red}{y=mx-(3m-6)}\;$ , and we want this line to intersect $\;E\;$ only at the given point, so we need the equation over $\;\Bbb F_7\;$ : $\;(mx-(3m-6))^2=x^3+2\;$, to have one single solution (the following is done modulo $\;7\;$ all along):

$$m^2x^2-2m(3m-6)x+9m^2-36m+36=x^3+2\implies$$

$$f(x)=x^3-m^2x^2+6m(m-2)x-2m^2+m+1=0$$

The above cubic has $\;x=3:\;f(3)=0 , \;$ as a root, of course. If we require this root to be double (as we need a single solution), also its derivative must vanish at $\;x=3\;$ :

$$f'(x)=3x^2-2m^2x+6m^2-5m\implies 0=f'(3)=-1-6m^2+6m^2-5m\implies$$

$$5m=-1\implies m=(-1)\cdot\overbrace{3}^{=5^{-1}}=-3=4$$

and that way we get the line

$$\color{red}{y=4x+1}$$

$\endgroup$
0
$\begingroup$

If the line $L$ intersects $E$ only at the given point $P$ (and the point $\mathcal O$ at infinity), then the intersection of $L$ and $E$ at $P$ must have multiplicity $2$, and so $L$ is the tangent line to $E$ at $P$. For an algebraic plane curve $\{p(x, y) = 0\}$, the tangent line at $P = (a, b)$ is $$p_x(a, b)(x - a) + p_y(a, b)(y - b) = 0 ,$$ where $p_x$ and $p_y$ are the (formal) partial derivatives of $p$.

In our case, $E$ is the zero set of $p(x, y) := x^3 - y^2 + 2$, so $p_x(x, y) = 3 x^2$, and thus $p_x(3, 6) = -1$. Likewise we get $p_y(3, 6) = 2$, and substituting in the above equation gives the equation $$-(x - 3) + 2(y - 6) = 0$$ for $L$. Multiplying both sides by $-3$ to eliminate the coefficient of $y$ and rearranging gives $$y = 4 x + 1.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.