Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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

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 - x_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, so $s = (3 x_1^2 + 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 its characteristic isn't 2 or 3.

share|cite|improve this answer
    
The first two sentences are very clear. The third sentence is not, and totally loses me. Could you break that paragraph down into a clearer progression? I don't know what s is, or where you got the two equations immediately thereafter. Moreover the sentence is grammatically weird, you wrote "You can check that if ... then .. and .. then..." Then and then doesn't make sense! Are x3 and y3 coordinates of the point you're terming s? – Aerovistae May 1 at 0:01

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.