Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How do you add two points P and Q on an elliptic curve over a finite field $\Bbb F_{p}$. For example: adding the points $(1,4)$ and $(2,5)$ on the curve $y^2 = x^3+2x+2$ over $\Bbb F_{11}$. I know one way involves drawing a straight through the two points P and Q and getting a third point R (P+Q) which means using a straight line equation and the elliptic curve equation. Any insights?

share|improve this question
5  
Take Silverman's book, or any other one where the addition law for the elliptic group is explained. It seems to be pretty lonhg to develop it here. –  DonAntonio May 5 '13 at 22:13

1 Answer 1

Consider the case of the curve $y^2 = x^3 + a x + b$ on $\mathbb{R}$ for starters. Let $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ be different points on the curve. You can check that if $s = (y_2 - y_1)/(x_2 - y_1)$, then $x_3 = s^2 - x_1 - x_2$ and $y_3 = y_1 + s (x_3 - x_1)$ then $(x_3, y_3)$ is on the curve and $(x_3, -y_3)$ is collinear with $P$ and $Q$. A computer algebra system like maxima is helpful here.

Adding a point to itself involves a tangent to the curve, and $s = (3 x_1 + a) / 2 y_1$ and $x_3 = s^2 - 2 x_1$ and $y_3 = y_1 + s (x_3 - x_1)$.

The same formulas are valid on any field, as long as the characteristic isn't 2 or 3.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.