0

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}

lioness99a
  • 4,943
  • 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? – Travis Willse Mar 06 '17 at 12:38
  • 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 – lioness99a Mar 06 '17 at 12:43

2 Answers2

1

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}$$

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
0

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.$$

Travis Willse
  • 99,363