3
$\begingroup$

I'm trying to add the points $(3,2)$ and $(5,5)$ on the elliptic curve $E: y^2 \equiv x^3 - 2 \mod 7$, of course working in the field $\mathbb{F}_7$.

Knowing that the secant line connecting the two points is given by $$y \equiv mx + a$$ we can solve and find $$m \equiv 5$$ $$a \equiv 1$$

Now here's where I think something goes wrong. Using the above expression for $y$, I should have values satisfying $$(5x+1)^2 \equiv x^3 - 2 \mod 7$$ Unfortunately, no values of $x$ satisfy this equality.

Can someone point out where I've gone wrong?

$\endgroup$
1
$\begingroup$

$(x^3-2) - (5x+1)^2 = x^3-25x^2-10x-3 \equiv (x-3)(x-3)(x-5)$
so the third point corresponds to $x=3$.

$\endgroup$
1
$\begingroup$

It's correct there is no third point. This just means the line $y = 5x+1$ is tangent to $(3,2)$ or $(5,5)$, and then the sum is the inverse of the tangent point, in this case $(3-2)$. (if the tangent line at $P$ intersects the curve at $Q$ then $P + P = -Q$ which implies that $P + Q = -P$).

Alternatively, use the addition formulae: suppose $P = (x_P, y_P)$, $Q = (x_Q, y_Q)$ with different $x$-coordinates then compute $R = P + Q = (x_R, y_R)$ as follows (all in the finite field):

  • $m = \frac{y_P - y_Q}{x_P - x_Q}$

  • $x_R = m^2 - x_P - x_Q$

  • $y_R = y_P + m(x_R - x_P)$

see this intro. In this case, if $x_P= y_P$, use $m = \frac{3x^2_P}{2y_P}$ to find the slope of the tangent. The latter also confirms the slope of the tangent at $(3,2)$ is indeed $5 = \frac{3 \cdot 9}{4}$ mod $7$.

$\endgroup$
  • $\begingroup$ yes you are right. how do you know its not the point at infinity ? you check the tangent at $P$ ? $\endgroup$ – reuns Mar 28 '17 at 9:23
  • $\begingroup$ @user1952009 the sum is $O$ iff the original points are inverses, of course. $\endgroup$ – Henno Brandsma Mar 28 '17 at 9:25

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.