0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $H(n)$ or $H(x)$ ? $\endgroup$ – Claude Leibovici Jun 6 at 3:11
  • 1
    $\begingroup$ 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). $\endgroup$ – Jyrki Lahtonen Aug 7 at 16:50
  • $\begingroup$ @JyrkiLahtonen I know that, but only one person commented, so I thought that it wouldn't matter. $\endgroup$ – Quote Dave Aug 7 at 18:00
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Quote Dave Aug 7 at 18:03
  • 1
    $\begingroup$ 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. $\endgroup$ – dan_fulea Aug 7 at 18:58
  • 1
    $\begingroup$ 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. $\endgroup$ – dan_fulea Aug 8 at 1:07
  • 1
    $\begingroup$ 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 $\endgroup$ – dan_fulea Aug 8 at 13:34
  • 1
    $\begingroup$ 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. $\endgroup$ – dan_fulea Aug 9 at 20:35

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.