# Point Addition on Elliptic Curves Over Finite Fields, Geometrically.

I am studying elliptic curves. A part of it is doing point addition between two points $$P$$ and $$Q$$, where $$P$$ and $$Q$$ are distinct points, on a curve $$y^2=x^3+ax+b (\bmod p)$$, where $$a$$ and $$b$$ are non-zero integers and $$p$$ is some prime, so that $$P+Q=R$$. My question is, is there a function, given $$x_p$$ and $$x_q$$, with the sign of $$y_q$$ known, that $$f(x_p,x_q)=x_r$$?

EDIT: It would also be nice to have a geometric approach to adding (and doubling) points on elliptic curves over finite fields.

• $H(n)$ or $H(x)$ ? – Claude Leibovici Jun 6 at 3:11
• Just in case nobody else said this. You really should NEVER replace your question with a totally different one. Many think that is quite rude (to those who answer the earlier version). – Jyrki Lahtonen Aug 7 at 16:50
• @JyrkiLahtonen I know that, but only one person commented, so I thought that it wouldn't matter. – Quote Dave Aug 7 at 18:00

No.

Some words follow, to explain how i understood the question, and why i claim the negative answer. An example may make the situation simpler to explain. Let us consider over $$F=\Bbb F_p$$, $$p=11$$, the elliptic curve with equation $$y^2=x^3 + x + 1$$. Then on the curve we have the rational points $$P_\pm = (0,\pm 1)\ ,\qquad Q_\pm=(1,\pm 5)\ .$$ Then

• the "two $$P$$-points" have the same $$x$$-component, $$x_p=0$$,
• the "two $$Q$$-points" have the same $$x$$-component, $$x_q=1$$,

but adding points in all four possible ways to combine deliver, here in sage:

sage: E = EllipticCurve( GF(11), [1, 1] )
sage: P0, P1 = E.point( (0, +1) ), E.point( (0, -1) )
sage: Q0, Q1 = E.point( (1, +5) ), E.point( (1, -5) )
sage: [ (P+Q).xy() for P in [P0, P1] for Q in [Q0, Q1] ]
[(4, 5), (2, 0), (2, 0), (4, 6)]


we get the above points, the first coordinate is either $$2$$, or $$4$$. So there is no "unique $$x_r$$" that can be associated only with the knowledge of $$x_p$$, $$x_q$$.

The reason can be simply explained by the fact, that the computation of $$R$$ depends of building the following slope $$m$$ in the affine plane of the rational points $$P(x_p,y_p)$$, $$Q(x_q,y_q)$$, $$m = \frac{y_p-y_q}{x_p-x_q}\ .$$ So exchanging signs in $$\pm y_p$$, $$\pm y_q$$ leads "very often" to a difference.

Bonus: Here are some further thoughts related to the geometrical construction of $$P+Q$$ and $$2P:=P+P$$ for two points $$P,Q$$ on some elliptic curve defined over some finite field $$F=\Bbb F_q$$, $$q$$ prime power (of a prime not equal to two, three maybe), or over an infinite field $$F=\Bbb Q$$ or $$\Bbb R$$ or $$\Bbb C$$, by an equation of the shape: $$E\ :\ y^2 =x^3+ax+b\ ,\ a,b\in F\ ,$$ where $$x^3+ax+b$$ has different roots in some algebraic closure of $$F$$.

We start with two $$F$$-rational points $$P_1(x_1,y_1)$$, and $$P_2(x_2,y_2)$$ in $$E(F)$$. In the generic case $$x_1\ne x_2$$ the equation of the line through the two points is of the shape $$y=mx+n$$, with $$m,n$$ depending on $$P_1$$, $$P_2$$. Then from \begin{aligned} y_1 &=mx_1+n\ ,\\ y_2 &=mx_2+n\ ,&&\text{ after subtraction we get}\\ y_1-y_2&=m(x_1-x_2)\ ,&&\text{ so we have the formula for the slope m}\\ m &=\frac{y_1-y_2}{x_1-x_2}\ . \end{aligned} For the first coordinate $$x_3$$ of $$\pm (P_1+P_2)=(x_3,\pm y_3)$$ we need only $$m$$, but $$n$$ can also be found easily from the above relations, then the third point on the line $$P_1P_2$$ (counting multiplicities) is by the definition of the operation $$+$$ on $$E(F)$$ the point $$-(P_1+P_2)=(x_3,-y_3)$$. (If we denote the coordinates in the sum $$P_1+P_2$$ by $$x_3,y_3$$.)

The points $$(x_1,y_1)$$, $$(x_2,y_2)$$, $$(x_3,-y_3)$$ satisfy thus both equations $$y^2=x^3+ax+b$$ and $$y=mx+n$$. We eliminate $$y$$ using the second equation from the first one, so $$x^3+ax+b-(mx+n)^2=0\ .$$ Explicitly: $$x^3-m^2x^2+\text{(lower degree terms in x)}=0$$ has then the roots $$x_1,x_2,x_3$$. Vieta gives us for the sum $$x_1+x_2+x_3 = m^2\ ,$$ so we obtain the formula for the first coordinate $$x_3$$, which is algebraically \boxed{\qquad \begin{aligned} x_3 &=-x_1-x_2+m^2 \\ &=-x_1-x_2+\left(\frac{y_1-y_2}{x_1-x_2}\right)^2\ . \end{aligned} \qquad} This is a good point to check the formula for some points on some curve. I will work first with $$E$$ given by $$y^2=x^3+x+1$$ over $$F=\Bbb F_{11}$$, ask for the sum of some random points $$P,Q$$ in $$E(F)$$. We ask for the implemented formula, thus getting $$P+Q$$ from sage, then i will implement with bare hands the above formula, also ask for the result for the same points.

sage: E = EllipticCurve( GF(11), [1, 1] )
sage: import random
sage: P = random.choice(E.points())
sage: Q = random.choice(E.points())
sage: P, Q, P+Q
((2 : 0 : 1), (0 : 10 : 1), (1 : 6 : 1))
sage: def x3(P, Q):
....:     """We compute the first component x3 of P=:(x1, y1), Q=:(x2, y2)
....:     using the formula x3 = -x1 -x2 + (y1-y2)^2/(x1-x2)^2
....:     Note that we assume x1 != x2, and that P, Q != infinit point"""
....:     x1, y1 = P.xy()
....:     x2, y2 = Q.xy()
....:     return -x1 -x2 + (y1-y2)^2/(x1-x2)^2
....:
....:
sage: x3(P, Q)
1
sage: # the abover is the first component of P+Q = (1, 6)


Let us use some "more convincing" framework.

sage: E = EllipticCurve( QQ, [1, 1] )
sage: E.rank()
1
sage: E.gens()
[(0 : 1 : 1)]
sage: G = E.point( (0, 1) )    # the generator
sage: P, Q = 7*G, -5*G
sage: P, Q
((-3596697936/8760772801 : 591456591665497/819999573400799 : 1),
(43992/82369 : 30699397/23639903 : 1))
sage: P+Q
(1/4 : -9/8 : 1)
sage: x3(P, Q)
1/4
sage: P-Q
(516800901506579137034097949153/116165201153061098261023776144
: 382844998133375068925120757216593508841494737/39592604638617085219380314122331748004030272
: 1)
sage: x3(P, -Q)
516800901506579137034097949153/116165201153061098261023776144


A last remark about doubling. We start with "$$P$$ and $$P$$", and need to get the corresponding line $$y=mx+n$$ again. We use the notation $$P(x_1,y_1)$$, compute $$2P=(x_3,y_3)$$, but only the first component. (The second one follows, typing is only harder.)

One possibility to proceed is as follows. The point $$P(x_1,y_1)$$ is on the curve with equation $$F(x,y)=0$$, where $$F(x,y)=x^3+ax+b-y^2$$. Let us write $$x=x_1+s$$, $$y=y_1+t$$ to get in the Taylor expansion of $$F$$ around $$(x_1,y_1)$$ quickly the linear term. Explicitly: \begin{aligned} F(x,y) &=(x_1+s)^3+a(x_1+s)+b-(y_1+t)^2 \\ &=\underbrace{(x_1^3+ax_1+b-y_1^2)}_{=0} +(3x_1^2s+as-2y_1t) +\text{(Higher order monomials in s,t)}\ .\\[3mm] \operatorname{Taylor}_1(F)(x,y) &= 3x_1^2s+as-2y_1t \\ &=(3x_1^2+a)(x-x_1)-2y_1(y-y_1)\ .\\[3mm] &\text{Compare with y=mx+n. So the needed slope m is} \\ m &=\frac{3x_1^2+a}{2y_1}\ .\\[3mm] &\text{Alternatively:} \\ m &= \lim\frac{y_2-y_1}{x_2-x_1} \\ &=\lim\frac{(y_2-y_1)(y_2+y_1)}{(x_2-x_1)(y_2+y_1)} \\ &=\lim\frac{y_2^2-y_1^2}{(x_2-x_1)(y_2+y_1)} \\ &=\lim\frac{(x_2^3+ax_2+b)-(x_1^3+ax_1+b)}{(x_2-x_1)(y_2+y_1)} \\ &=\lim\frac{x_2^2+x_1x_2+x_1^2+a}{y_2+y_1} \\ &=\frac{x_1^2+x_1x_1+x_1^2+a}{y_1+y_1} \\ &=\frac{3x_1^2+a}{2y_1}\ . \end{aligned} (The limit is taken for $$(x_2,y_2)$$ converging on the curve to $$(x_1,y_1)$$. From here, we have the same, so $$x_3=-x_1-x_1+m^2$$. Computer check:

sage: def x3_for_double(P):
....:     """We compute the first component x3 for 3P for P=:(x1, y1),
....:     using the formula x3 = -2x1 + (3*x1^2+a)^2/4/y1^2
....:     """
....:     x1, y1 = P.xy()
....:     a = P.curve().a4()
....:     m = (3*x1^2 + a) / 2 / y1
....:     return -2*x1 + m^2
....:
sage: twoP.xy()[0]    # first component of 2P
23419679382776533016338728874246651427713/12258805697617629893689847027495187248836
sage: x3_for_double(P)
23419679382776533016338728874246651427713/12258805697617629893689847027495187248836

sage: # here, P has the last value used above
sage: P
(-3596697936/8760772801 : 591456591665497/819999573400799 : 1)


Note: All the above is "naive and standard", but i tried to write down explicitly the algebraic geometry computations. Monographs do not have the space for this, courses do not have the time.

• First, how is $(1,5)$ a point? And two, lets say the sign of $y_p$ is known. Even if the sign of $y_q$ is negative or positive, would there be a difference in $x_r$? – Quote Dave Aug 7 at 18:03
• Let us see if $(1,5)$ is a point. (Sage would not accept the code else.) We have to check $5^2=1^3+1^1+1$, which holds over the field $F$ with $11$ elements. (It is natural to look for examples over finite fields, when typing denominators may be soon an issue over rationals when adding points. And the OP also mentions some modulo $p$.) Then the "sign" makes no sense, which is for instance the sign of $5$, or of $6$ in the field $F$ with $11$ elements? "Knowing which one of the values of $\pm y$" of a point $(x,y)$ is taken may lead to a function $f$ as in the $OP$, but not an algebraic one. – dan_fulea Aug 7 at 18:58
• Yes, that's the game. You may find it useful to play with sage, which covers in a simple and structural way (using the language of mathematics) all existing algorithms concerning elliptic curves (over $\Bbb Q$ and/or over a finite field). Programming knowledge is an advantage, but simply using it as a command line tool may also be very useful. For instance doc.sagemath.org/html/en/constructions/… but many other documented features. – dan_fulea Aug 8 at 1:07
• Then you're home, sage is written in python, collects all existing free and less free maths software (alias CAS ~ computer algebra systems) like pari/gp, Cremona database, maxima, R, etc. and uses python as a "general parser", most sage libraries are written in python + batteries, numpy and/or scipy are already included in implemented algorithms (or sage uses the existing implementation), but can also be imported. Sage comes with the sage console, a kind of ipython (with preprocessing). Equations are of course also supported. Questions can be directed to ask.sagemath.org/questions – dan_fulea Aug 8 at 13:34
• Remember once for all times, we are working modulo $11$. So computations like addition, multiplication can be done in $\Bbb Z$, but at the end the result is taken modulo $11$, we are working in $$F=\Bbb F_{11}=\Bbb Z/11\ ,$$ so $\dots=-33=-22=-11=0=11=22=33=\dots$, and $\dots=-33+1=-22+1=-11+1=0+1=11+1=22+1=33+1=\dots$, and i never write that "modulo eleven", since it is clear from the context. We already saw that $25=3$, now we are at the point with $23=1$. The level of complication when dealing with elliptic curves is high, please fix first the needed knowledge. This is my last comment. – dan_fulea Aug 9 at 20:35