First application: sums on an elliptic curve

Our goal now is to produce the first real application: we want to write a function sum that will compute the sum of two points on an elliptic curve, using the curve's group structure.

Before we start, we have to decide how we want to ``describe'' the curve and arbitrary points. We can start by assuming that the curve is given in Weierstrass form

$$y^2 = x^3 + a x^2 + b x +c$$ (2)

so that the curve is determined by the tuple $(a,b,c)$. Fortunately, python knows what a tuple is:

>>> curve = (0,3,0)
>>> curve[0]
0
>>> curve[1]
3
>>> curve[2]
0

The first line stores in curve the tuple defining the elliptic curve $y^2=x^3+3z$. The next lines show how you can access the components of a tuple. Notice that the coordinates are numbered beginning from 0.

Points can be stored in the same way, using tuples with two entries.

>>> p1=(1,2)

Now the idea is simple: if $p_1 = (x_1,y_1)$ and $p_2 = (x_2,y_2)$, $p_3 = p_1 + p_2$ satisfies² $p_3 = (x_3,y_3)$ with

$$x_3 = \lambda^2 - a - x_1-x_2 \quad y_3 = -(\lambda x_3 + \nu)$$

with

$$\lambda = \frac{y_2-y_1}{x_2-x_1} \quad \nu=y_1-\lambda x_1.$$

We write our (first?) version of the sum function. Still working on the elliptic.py file we write:

def sum1(cur,p1,p2):
    """compute p1+p2 on the elliptic curve cur"""
    lam = (p2[1]-p1[1])/(p2[0]-p1[0])
    nu = p1[1] - lam*p1[0]
    x3 = lam**2 - cur[0] - p1[0] - p2[0]
    y3 = -(lam * x3 + nu)
    return (x3,y3)

Then we reload the elliptic.py file (we won't mention this step in the future, so make sure you remember to do it on your own). We pick p2 on the curve and compute p1+p2:

>>> p2=(0,0)
>>> elliptic.sum1(curve,p1,(0,0))
(3, -6)

Excellent! Now we can play with our sum1 function. According with [1, page 31], the points $P_1 = (-1,4)$ and $P_2 = (2,5)$ are on the curve $y^2=x^3 + 17$. Let's compute their sum:

>>> curve17=(0,0,17)
>>> p1=(-1,4)
>>> p2=(2,5)
>>> elliptic.sum1(curve17,p1,p2)
(-1, -4)

So, we obtain $P_1 + P_2 = (-1,-4)$... but this is not the result obtained in [1]. After thinking for a while you may discover that we are wrong! What we missed is that when we compute lam, we did it as a quotient of two integer numbers, so python computed the integer division that is not what we wanted. How do we fix this problem? One possibility would be to convert our numbers into floating point numbers so that python will compute the appropriate quotient. But the problem with this approach is the precision loss involved in using floating point operations. Instead, we will ``teach'' python about rational numbers. For that we will use the file Rat.py that you can obtain from the same place you obtained this document.

We modify the elliptic.py file to:

from Rat import rat

def on_curve(x,y):
    """See if (x,y) is on the curve y**2==x**3+3x"""
    return y**2==x**3+3*x

def sum1(cur,p1,p2):
    """compute p1+p2 on the elliptic curve cur"""
    lam = (p2[1]-p1[1])/rat(p2[0]-p1[0])
    nu = p1[1] - lam*p1[0]
    x3 = lam**2 - cur[0] - p1[0] - p2[0]
    y3 = -(lam * x3 + nu)
    return (x3,y3)

There are two changes: the first line instructs python to import the function rat (that creates a rational number) from the file (module) Rat.py. Then, in the definition of lam we use rat to turn the denominator into a rational number. This change will force python to perform a rational quotient so that lam gets the proper value:

>>> elliptic.sum1(curve17,p1,p2)
(Rat(-8,9), Rat(-109,27))

That is, $P_1 + P_3 = (-\frac{8}{9}, -\frac{109}{27})$ in accordance with [1].

Next we want to use sum1 to compute $2 P_1 = P_1+P_1$:

 >>> elliptic.sum1(curve17,p1,p1)
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "elliptic.py", line 9, in sum1
    lam = (p2[1]-p1[1])/rat(p2[0]-p1[0])
  File "Rat.py", line 151, in __rdiv__
    return Rat(a) / b
  File "Rat.py", line 145, in __div__
    return rat(a.__num * b.__den, a.__den * b.__num)
  File "Rat.py", line 38, in rat
    return Rat(num, den)
  File "Rat.py", line 45, in __init__
    raise ZeroDivisionError, 'rat(x, 0)'
ZeroDivisionError: rat(x, 0)

Wow! That was something... wrong. If you look at the last output line you will see the key: we are dividing by 0! Why would that be? When we are trying to compute lam we divide by the difference of the $x$-coordinates of the two points... that is 0 if the points are the same! We have to use the appropriate doubling formula, again from [1]: for $P_1 + P_1$, we have to use

$$\lambda = \frac{3x_1^2+2ax_1+b}{2y_1}.$$

Taking this into account, sum1 becomes:

def sum2(cur,p1,p2):
    """compute p1+p2 on the elliptic curve cur"""
    if p1==p2:
        lam = (3*p1[0]**2 + cur[0]* 2 *p1[0] + cur[1])/rat(2*p1[1])
    else:
        lam = (p2[1]-p1[1])/rat(p2[0]-p1[0])
    nu = p1[1] - lam*p1[0]
    x3 = lam**2 - cur[0] - p1[0] - p2[0]
    y3 = -(lam * x3 + nu)
    return (x3,y3)

Here we use the if ... else construction: it does the obvious thing, that is, if p1 equals p2 it uses the first definition of lam, otherwise it uses the second definition. Notice the important role of indentation: it determines what is executed in each case (other languages enclose these ``blocks'' of code with ``{}''; in python it is just indentation).

Now we are ready to compute the sum of two points, even if they are equal:

>>> elliptic.sum2(curve17,p1,p1)
(Rat(137,64), Rat(-2651,512))

Exercise 4.1   Use sum2 to compute sums and multiples of points on $y^2=x^3 + 17$.

Exercise 4.2   Find $-P_1$. Use sum2 to compute $P_1 + (-P_1)$.

Did you solve Exercise 4.2? Go ahead: do it!

Now that you tried to compute $P_1 + (-P_1)$, can you see what is wrong with sum2 in this case? The problem is that even if $P_1 \neq -P_1$, they have the same $x$-component, so in the computation of $\lambda$ the denominator still vanishes. In order to fix it, we have to understand what we are doing: $P_1 + (-P_1)$ should be the null element (for the sum on the curve), but that point is the point at infinity (for the curve in Weierstrass form), which is not given by a pair of numbers. So we have to represent the null element in some other way. One possibility is as follows:

def sum3(cur,p1,p2):
    """compute p1+p2 on the elliptic curve cur"""
    if p1==p2:
        lam = (3*p1[0]**2 + cur[0]* 2 *p1[0] + cur[1])/rat(2*p1[1])
    elif p1[0]==p2[0]:
        return "null_element"
    else:
        lam = (p2[1]-p1[1])/rat(p2[0]-p1[0])
    nu = p1[1] - lam*p1[0]
    x3 = lam**2 - cur[0] - p1[0] - p2[0]
    y3 = -(lam * x3 + nu)
    return (x3,y3)

That is, when we detect a $P+(-P)$ situation we simply return the string "null_element".

>>> elliptic.sum3(curve17,p1,(-1,-4))
'null_element'

Exercise 4.3   Modify sum3 so that it can accept "null_element" as input and produces the correct sum. Check that you get the correct values for sum4(curve17,"null_element",p1), sum4(curve17,p2,"null_element") and sum4(curve17,"null_element","null_element"). This function, the final, most general, version will be called sum.

Exercise 4.4   Write the function inverse that takes a point on an elliptic curve and produces the inverse of that point. Make sure that it also works for the "null_element".