1
$\begingroup$

I just have a very basic question. For two distinct points $P_1, P_2$ with non-zero components on an elliptic curve $C$ given by $y^2 = x^3 + Ax + B$, I'm trying to derive the addition formula using the fact that the constant term of a monic cubic is equal to the negative of the product of the roots. Here's what I have so far, but I'm either making a mistake or missing the necessary algebraic trick.

Let $P_i = (x_i, y_i)$ for $i \in \{1,2\}$. Then the line from $P_1$ to $P_2$ is given by $y = m(x - x_1) + y_1$, where $m = (y_2 - y_1)/(x_2 - x_1)$. Then $$ y^2 = x^3 + Ax + B \implies f(x) = x^3 + Ax + B - (m(x-x_1) + y_1)^2$$ We can ignore all of the non-constant terms, so rewriting, we need to show that: $ (-mx_1 + y_1)^2 - B $ is the product of the roots. $$ m^2x_1^2 - 2mx_1y_1 + y_1^2 - B = m^2x_1^2 - 2mx_1y_1 + x_1^3 + Ax_1 $$ $$ \frac{m^2x_1^2 - 2mx_1y_1 + x_1^3 + Ax_1}{x_1x_2} = \frac{m^2x_1 - 2my_1 + x_1^2 + A}{x_2}$$ $$ \frac{m^2(x_2 + \frac{(y_1 - y_2)}{m}) - 2mx_1y_1 + x_1^3 + Ax_1}{x_1x_2} = \frac{m^2x_2 - my_1 - my_2 + x_1^2 + A}{x_2} $$ $$ = m^2 + \frac{-m(y_1 + y_2) + x^2_1 + A}{x_2} $$

I don't see how $\frac{-m(y_1 + y_2) + x^2_1 + A}{x_2} = -x_1 - x_2$ or even how to eliminate the $A$ term, so I must be making a mistake. Any help would be appreciated.

$\endgroup$
16
  • $\begingroup$ Given $(x_1,y_1),(x_2,y_2)\in E$, $x_1 \ne x_2$ you want a $t$ such that $(x_1+t (x_2-x_1),y_1+t (y_2-y_1)) \in E$. This is a cubic polynomial equation $P(t)=0$ with $3$ solutions : $t= 0,t=1$ and a 3rd one $T$, which means $P(t) = C t (t-1)(t-T)$, you obtain the value of $T$ from $p(-1)= -2 C (T+1)$. $\endgroup$
    – reuns
    Commented Oct 8, 2018 at 21:17
  • $\begingroup$ I don't see how to derive $x_3 = m^2 - x_1 - x_2$ from this. $\endgroup$ Commented Oct 8, 2018 at 21:39
  • $\begingroup$ ? The goal is to find $(x_3,y_3 )= (x_1+T (x_2-x_1),y_1+T (y_2-y_1)) \in E$. I changed your notation because your motivation for introducing $m$ and $ m(x - x_1) + y_1$ wasn't clean. $\endgroup$
    – reuns
    Commented Oct 8, 2018 at 21:41
  • $\begingroup$ I'm working out of a problem in a book - have to derive the formula given, which is $x_3 = m^2 - x_1 - x_2$. I'm not understanding your notation either - are $P$ and $p$ different? What is $p(-1)$? $\endgroup$ Commented Oct 8, 2018 at 21:54
  • $\begingroup$ $(x_1+t (x_2-x_1),y_1+t (y_2-y_1)) \in E$ means $P(t) = (y_1+t (y_2-y_1))^2 - (x_1+t (x_2-x_1))^3-A (x_1+t (x_2-x_1))-B = 0$. Write $P(t) = -(x_2-x_1)^3 t (t-1) (t-T)$ then $P(-1) = (x_2-x_1)^3 2(T+1)$ and your point is $(x_3,y_3 )= (x_1+T (x_2-x_1),y_1+T (y_2-y_1)) \in E$ and $(x_1,y_1)+(x_2,y_2)+(x_3,y_3) = O$ defines a group law $\endgroup$
    – reuns
    Commented Oct 8, 2018 at 21:58

1 Answer 1

2
$\begingroup$

I’m writing this after almost a glass of wine, hope I don’t get the rest of it on my face.

This is just not the strategy I know, and that is by comparison so much shorter than what you’ve written that I don’t have courage to read the $n+1$ comments.

The line joining the $P_i$ will be given by $\ell:Y=mX+n$ for $n$ a rational expression that need not concern us. Then to get the intersection of $\ell$ with the curve of course you look for the roots of $g(X)=X^3+AX+B-(mX+n)^2$, when you know that $(X-x_1)(X-x_2)$ divides this. When you divide, you get a quotient $X-(m^2-x_1-x_2)$. You don’t need to do the division out — you just need to make sure that the $X^2$-coefficients are all right.

There’s your desired formula. If you try to use the constant term of $g$, you will, in my setup, get bogged down with the formula for $n$, a mess. I really don’t recommend doing it this way unless you are interested in an intellectual exercise that is, in my mind, going the long way round Robin Hood’s barn.

$\endgroup$
2
  • $\begingroup$ Thank you, that makes perfect sense. I guess that you're using the fact that the roots of a monic cubic divide the constant term to save on doing all of the division - which makes me think that the problem intends for incredibly tedious algebra, but I'm self-studying, so I will remember your approach, rather than continuing to circle Robin Hood's barn. $\endgroup$ Commented Oct 9, 2018 at 1:49
  • $\begingroup$ Yes and no, @user1447447. What I was using was the fact that the next-highest coefficient is minus the sum of the roots. We know that two roots are the $x_i$, and the third is $-x_1-x_2+m^2$. I knew that the polynomial $(X-x_1)(X-x_2)$ must divide the cubic I mentioned; I’ve actually performed the full division, and the equality of the product of the three roots to the constant term in what you see above really did work out, but only after some tiresome manipulations, as I recall. It’s been a long time… $\endgroup$
    – Lubin
    Commented Oct 9, 2018 at 3:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .