Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

How do we add the integer points $P=(-1, 4)$ and $Q=(2, 5)$ on the elliptic curve of the form $y^2=x^3+17$ ?

share|improve this question

1 Answer 1

up vote 7 down vote accepted

It happens that a line usually (not always) cuts three points in a elliptic curve by the Bezout theorem. This is the case for the points and the curve you are asking for.

So the sum of two points are defined like the inverse of the third point intercepted by the line that cut $P$ and $Q$ (let's name it $R$). So we need to find $-R$ because $P+Q=-R$ by definition (the inverse is calculated by multiplying the $y$ component of $R$ by $-1$).

The line equation that cuts $P$ and $Q$ has the form $y=ax+b$. So let's calculate $a$ (the slope) with:

$ a=\frac{5-4}{2+1}=\frac{1}{3} $

To calculate b, we use the fact that we know the $x$ and $y$ values for $p(-1,4)$:

$ 4=a*-1+b $

Solving this equation we get $b=\frac{13}{3}$. So, the equation line that cuts $P$ and $Q$ is $y=\frac{1}{3}x+\frac{13}{3}$.

The third point can be obtained by solving the next equation system (formed by the equations of the line and the curve):

$y=\frac{1}{3}x+\frac{13}{3}$

$y^2=x^3+17$

This system has three solutions (as expected):

$x=-1, y=4$ (this is the point $P(-1,4)$)

$x=2, y=5$ (this is the point $Q(2,5)$)

$x=-\frac{8}{9}, y=\frac{109}{27}$ (the point $R$)

So the sum of $P$ and $Q$ is $-R$, this is:

$P+Q=-R=(-\frac{8}{9}, -\frac{109}{27})$

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.