elliptic-curvesfunctionsmodular arithmetic
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.
Instead of following blindly Wikipedia's formulas, it is best to understand how to calculate $P+Q$, or $P+P$, given an elliptic curve. Let us assume for simplicity that the curve is given by $E:y^2=x^3+Ax+B$, and $P,Q\in E$.
In order to find $P+Q$, first find the equation of the line $L$ through $P$ and $Q$, find the third point $R$ of intersection of $L$ and $E$. Then $P+Q+R=\mathcal{O}$, so that $R=-(P+Q)$. In this case $-(x_0,y_0)=(x_0,-y_0)$, so we can find $P+Q$ as $-R$.
In order to find $P+P$, first find the tangent line $L$ to $E$ at $P$, and find the third point $R$ of intersection of $L$ and $E$. Then, $2P+R=\mathcal{O}$, and so $2P=-R$.
In your case, $E: y^2=x^3+1$ and $P=(0,1)$. The tangent line is $y=1$, and it turns out that this line has a triple point of intersection with $E$, thus $R=P$. In particular, $2P=-R=-P$, and so $3P=\mathcal{O}$.
Another example with the same curve $E$: let $P=(2,3)$ and $Q=(0,1)$. The line through $P$ and $Q$ is $y=x+1$, and the third point of intersection is $R=(-1,0)$. Since $R=-R$, we obtain $P+Q=(-1,0)$.
Finally, here is a picture of $P=(2,3)$, $2P$, $3P$, $4P$, and $5P$, which shows that $6P=\mathcal{O}$.
You may be confusing the third point, say $S$, of intersection of $E$ and the line through $P$ and $Q$ with the point $P + Q = R$. Determining $S$ is just the first step in determining $R$. $R$ is, in turn, the third point of intersection of $E$ and line through $S$ and the zero point $O$. Wikipedia, as is traditional, chooses $O$ to be the point at infinity $\, 0:1:0 \,$ in the projective plane. With that choice for the zero point, the line through $S$ and $O$ is vertical, so, because $E$ is symmetric with respect to the $x$-axis (because $y$ appears only as $y^2$ in the equation for $E$), we just need to change the sign of the $y$-coordinate of $S$ to get $R$.
We now derive the Wikipedia formulas based on the two steps described above. The equation of the line through $P$ and $Q$ is $$y = y_p + \lambda (x - x_p).$$ Substitute that expression for $y$ into $y^2 = x^3 + ax + b$ to get $$x^3 - \lambda^2x^2 +(a + 2\lambda^2 x_p - 2\lambda y_p)x + b - (\lambda x_p - y_p)^2 = 0.$$ The three solutions to that cubic equation give the $x$-coordinates $x_p, x_q, x_s$ of the three points of intersection of the line with $E$. From Vieta's first formula, we see that the sum of those $x$-coordinates is $\lambda^2$ so that $x_p + x_q + x_s = \lambda^2$. When we reflect $S$ over the $x$-axis, the $x$-coordinate does not change, so $x_r = x_s$. Thus, $$x_r = \lambda^2 - x_p - x_q.$$ Using the equation of the line, \begin{align} y_s & = y_p + \lambda (x_s - x_p)\\ & = y_p + \lambda (x_r - x_p) \end{align} When we reflect $S$ over the $x$-axis, the sign of the $y$-coordinate changes, i.e., $y_r = -y_s$. Thus, $$y_r = \lambda (x_p - x_r) - y_p.$$
Best Answer
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
but adding points in all four possible ways to combine deliver, here in sage:
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.
Let us use some "more convincing" framework.
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:
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.