2
$\begingroup$

Supposing I have an elliptic curve E(K): y^2 = x^3 + Ax + B with char(K) != 2,3, why do the formulas for EC addition work in any field. The formulas make sense in ℝ, for example we calculate the slope between the two points or if we add the same point, we calculate the tangent line with derivation of the EC formula.

But as soon as we move to a finite field, why should these formulas work? Why does e.g. the formula for the slope of the line between two points or a "tangent" (which lives in the "continuous" world) make sense?

Is there any literature that highlights this problem? My background is that of an undergraduate student, but I am willing to read more advanced books if it answers the question.

Thanks in advance!

$\endgroup$
  • 1
    $\begingroup$ Basically it is because if you plug in the equation of a line, $y=mx+b$, to the equation of the elliptic curve, you get a cubic equation in the unknown $x$. Furthermore, the coefficients will be in the field $K$ that contains $A,B,m,b$. If you picked the line through a pair of points on the curve (with coordinates in $K$), then you know two solutions for the $x$, and Vieta relations imply that the third is also in that same field. If your line is the tangent line, this implies that the $x$-coordinate of the point of tangency is a double root of that cubic, and the same argument goes thru. $\endgroup$ – Jyrki Lahtonen Mar 22 at 10:46
  • 1
    $\begingroup$ Basically tangent line to the curve at the point $(x_0,y_0)$ can be replaced with the purely algebraic the unique line $y=mx+b$ such that the equation $(mx+b)^2=x^3+Ax+b$ has a double root at $x=x_0$. $\endgroup$ – Jyrki Lahtonen Mar 22 at 10:47
  • 1
    $\begingroup$ @JyrkiLahtonen That looks like it really should've been an answer post. $\endgroup$ – Arthur Mar 22 at 10:58
3
$\begingroup$

When going from continuous fields ($\Bbb R$ and $\Bbb C$, and to a lesser extent $\Bbb Q$) to something like a finite field, you are right that the geometric intuition fails. However, nothing is stopping the algebra from working exactly as before (or, at least, almost exactly like before; as you pointed out, characteristic 2 and 3 mess with things when working with quadratic and cubic polynomials).

Say we have a finite field $K$. Then the line between $(a, b)$ and $(c, d)$ in $K^2$ is simply the set of $(x, y)\in K^2$ which satisfy a linear equation $$ mx + ny + k = 0 $$ where $m, n, k$ are chosen so that the equation is satisfied for $(a, b)$ and $(c, d)$ (if the two points are distinct, then there is exactly one viable choice of $m, n, k$ up to scaling).

A tangent is a bit more tricky, but as we know from the continuous case, a line $mx + ny + k = 0$ which has a point $(a, b)$ in common with $E$ is tangent with $E$ at that point if the intersection at $(a, b)$ has degree greater than $0$. And the degree of the intersection can be found purely algebraically, for instance by looking at $K[x, y]/(mx+ny + k)\cong K[z]$ and considering whether $x^3 + Ax + B - y^2$ has a multiple root at $(a, b)$.

So the moral of the story is that even though the geometric interpretation doesn't make as much sense, we keep the geometric terms and define them algebraically instead, and much of the intuitive results from the continuous case carry right over to the discrete case.

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