Elliptic Curve Arithmetic over the Real Numbers

by Judith Koeller, University of Waterloo, Canada, jakoelle@math.uwaterloo.ca

Note: This worksheet demonstrates the use of Maple for elliptic curve arithmetic over the real numbers. Users may choose the parameters of an elliptic curve, and explore the Third Point of intersection, addition of points, point doubling and scalar multiplication. The resulting computations are displayed graphically.

2004 Judith Koeller

Elliptic curve arithmetic has useful applications in cryptography. Many texts treat the material in an algebraic way or provide only very few geometric illustrations. An exploration of the geometry of elliptic curve arithmetic gives a much deeper insight into the topic. This worksheet explores some basic concepts in elliptic curve groups over the real numbers.It is meant as a companion to a course or seminar in elliptic curves.

Arithmetic over elliptic curves is based on the fact that a secant line between a pair of points on a curve (almost always) intersects the curve at a unique third point. Arithmetic over elliptic curves is based on this Third Point property. The property can be proven algebraically, but experimentation with pairs of points gives the user a much stronger intuitive sense of the property. This worksheet includes a Third Point maplet that allows users to select pairs of points on an elliptic curve and demonstrates geometrically the third point of intersection.

The rule for addition of two points on an elliptic curve use a geometric construction with the third point of intersection. The Addition maplet allows users to select pairs of points and see the resulting addition.

The rule for doubling a point uses a variant of the Third Point property - one that promises a unique point of intersection with the tangent line to an elliptic curve. The Doubling maplet allows users to select a point P on a curve, and constructs the point 2P using the tangent line and intersection.

Applications of elliptic curves to cryptography use Scalar multiplication of a point. The Repeated Addition maplet allows the user to select a point on a curve and computes 2P,3P,4P,...

Warning, the name changecoords has been redefined

Run this execution group to initialize some functions common to the other applets.

Warning, the name changecoords has been redefined

Warning, `e` is implicitly declared local to procedure `CurvePoint`

Third Point Maplet

Provided that is not 0, an elliptic curve has an interesting property: a line through any two points on the curve intersects the curve in exactly one more point. The only exception to this is when the two points are reflections of each other in the x-axis. In that case, the line connecting them is a vertical line, and it does not intersect the curve in a third point.

You can convince yourself of this fact using the following maplet. When you choose different points P and Q on an elliptic curve, the applet will demonstrate the unique third point -R where the line intersects the curve.

#"Third Point" Maplet

with(Maplets[Elements]):
with(plots):

# Given x,y coordinate of points P and Q on the curve,
# returns the x coordinate of the point -R, the third point of intersection of the curve with the line through P and Q

ThirdPointx := proc(a,xP,yP,xQ,yQ)
    local xR, m:

    if (xP=xQ) then
        if (yP=-yQ) then
             xR := infinity:
        else
             xR := 0:
        end if:
    else
            m:= (yQ-yP)/(xQ-xP):
            xR:= m^2-xP-xQ:
    end if:

    return xR:
end:

# Given x,y coordinate of points P and Q on the curve,
# and the x coordinate of R=P+Q,
# returns the y coordinate of the point -R, the third point of intersection of the curve with the line through P and Q

ThirdPointy := proc(a,xP,yP,xQ,yQ,xR)
    local yR,m:

    if (xP=xQ) then
        if (yP=-yQ) then
             yR := infinity:
        else
             yR := 0:
        end if:
    else
            m:= (yQ-yP)/(xQ-xP):
            yR:= -yP + m*(xP-xR):
    end if:

    return -yR:
end:

# Given parameters a and b for an elliptic curve, and points P and Q on the curve, displays the unique third point -R where the line through P and Q intersects the curve

eThirdPoint := proc(a,b,xP,yP,xQ,yQ, xR,yR)
    local curve, pointP, textP,  pointQ, textQ, m, pointR, textR, textmR, SecantLine, ReflectionLine, xmin, xmax, ymin, ymax, GridSize:
    GridSize := 20:
    try
            if (4*a^3+27*b^2 = 0) then
                #For this value of discriminant, the elliptic curve does not form a group.

                    curve := implicitplot({y^2=x^3+a*x+b},x=-10..10,y=-6..6,grid=[GridSize,GridSize],titlefont=[TIMES,ITALIC,18],title="This choice of a and b has 4a^3+27b^2=0.",color=green):
                display(curve);
        else        
                if (xP=xQ) then
                     if (yP = -yQ) then
                        # P+Q is the point at infinity.

                        # Calculate the viewing rectangle
                        xmin := min(-4,xP,xQ)-1:
                        xmax := max(4,xP,xQ)+1:
                        ymin := min(-6,yP,yQ)-1:
                        ymax := max(6,yP,yQ)+1:

                        # Plot the curve, P, a vertical tangent and the result of the computation.
                            curve := implicitplot({y^2=x^3+a*x+b},x=xmin..xmax,y=ymin..ymax,grid=[GridSize,GridSize],titlefont=[TIMES,ITALIC,18],title="The line through P and Q is vertical.",color=green):
                            pointP := pointplot({[xP,yP]},color=red):
                        textP :=textplot({[xP,LabelYCor(yP,ymin,ymax),"P"]},font=[TIMES,BOLDITALIC,12],color=red):
                            pointQ := pointplot({[xQ,yQ]},color=magenta):
                        textQ :=textplot({[xQ,LabelYCor(yQ,ymin,ymax),"Q"]},font=[TIMES,BOLDITALIC,12],color=magenta):
                        SecantLine := implicitplot({x=xP},x=xmin..xmax,y=ymin..ymax,grid=[GridSize,GridSize], color=black):
                            display(curve,pointP, textP,pointQ,textQ, SecantLine);
                     else
                        #P=Q

                        # Calculate the viewing rectangle
                        xmin := min(-4,xP,xR)-1:
                        xmax := max(4,xP,xR)+1:
                        ymin := min(-6,yP,yR,-yR)-1:
                        ymax := max(6,yP,yR,-yR)+1:

                        m:= (3*xP^2 + a)/(2*yP):
                        # Plot the curve, P, Q, the tangent and the result of the computation.
                            curve := implicitplot({y^2=x^3+a*x+b},x=xmin..xmax,y=ymin..ymax,grid=[GridSize,GridSize],color=green,titlefont=[TIMES,ITALIC,18],title="Choose distinct points P and Q."):
                            pointP := pointplot({[xP,yP]},color=red):
                        textP :=textplot({[xP,LabelYCor(yP,ymin,ymax),"P,"]},font=[TIMES,BOLDITALIC,12],color=red):
                        textQ :=textplot({[xP+0.5,LabelYCor(yP,ymin,ymax),"Q"]},font=[TIMES,BOLDITALIC,12],color=magenta):
                        pointR := pointplot({[xR,yR],[xR,-yR]},color=blue):
                            display(curve,pointP,textP,textQ);
                     end if:
                
                else
                        # Calculate the viewing rectangle
                        xmin := min(-4,xP,xQ,xR)-1:
                        xmax := max(4,xP,xQ,xR)+1:
                        ymin := min(-6,yP,yQ,yR)-1:
                        ymax := max(6,yP,yQ,yR)+1:
                        
                        m:= (yQ-yP)/(xQ-xP):

                        #Plot the curve, P, the tangent line, its intersection with the curve (-R), and R=2P.
                            curve := implicitplot({y^2=x^3+a*x+b},x=xmin..xmax,y=ymin..ymax,grid=[GridSize,GridSize],color=green):
                            pointP := pointplot({[xP,yP]},color=red):
                        textP :=textplot({[xP,LabelYCor(yP,ymin,ymax),"P"]},font=[TIMES,BOLDITALIC,12],color=red):
                            pointQ := pointplot({[xQ,yQ]},color=magenta):
                        textQ :=textplot({[xQ,LabelYCor(yQ,ymin,ymax),"Q"]},font=[TIMES,BOLDITALIC,12],color=magenta):
                        pointR := pointplot({[xR,yR]},color=blue):
                        textR := textplot({[xR,LabelYCor(yR,ymin,ymax),"-R"]},font=[TIMES,BOLDITALIC,12],color = blue):
                        SecantLine := implicitplot({y-yP=m*(x-xP)},x=xmin..xmax,y=ymin..ymax,grid=[GridSize,GridSize], color=black):
                            
                        display(curve,pointP, textP,pointQ, textQ, SecantLine, pointR,textR);
                        #display(curve);
                end if:
        end if;
    catch:
        textP :=textplot({[1,1,xP]},font=[TIMES,ITALIC,12],color=violet):
        curve := implicitplot({y^2=x^3+a*x+b},x=-6..6,y=-6..6,grid=[GridSize,GridSize],color=green,titlefont=[TIMES,ITALIC,18],title="There was an error generating this computation"):
        display(curve);
    end try;
end:


ThirdPoint:=()->Action(
        Evaluate('xP' = 'xPCor(a,b,P)'),
        Evaluate('yP' = 'CurvePoint(a,b,xP,yPPos)'),
        Evaluate('xQ' = 'xPCor(a,b,Q)'),
        Evaluate('yQ' = 'CurvePoint(a,b,xQ,yQPos)'),
        Evaluate('xR' = 'ThirdPointx(a,xP,yP,xQ,yQ)'),
        Evaluate('yR' = 'ThirdPointy(a,xP,yP,xQ,yQ,xR)'),
        Evaluate('PL1' = 'eThirdPoint(a,b,xP,yP,xQ,yQ,xR,yR)'),
        Evaluate('eq'= 'y^2=x^3+a*x+b')
):

ThreePointMaplet := Maplet(
 Window('title'= "Elliptic Curves: Third Point on the Line through P and Q",
 BoxLayout['BL1'](
  BoxColumn(
 BoxRow('halign'=left,"Choose an Elliptic Curve: ", MathMLViewer['eq']('value' = MathML[Export](y^2=x^3-x+6), 'height'=50, 'width'=180)),
 BoxRow('halign'=left, "a: ", Slider[a](-10..10, -1,'showticks','filled'=true,'majorticks'=5,'onchange'=ThirdPoint(),'minorticks'=1,'snapticks'=false),
"b: ", Slider[b](-10..10, 6,'showticks','filled'=true,'majorticks'=5,'onchange'=ThirdPoint(),'snapticks'=false,'minorticks'=1)),
 BoxRow(Plotter['PL1'](eThirdPoint(-1,6,3,-5.477,1,-2.449,-1.708,1.65))),
  BoxRow('halign'=left,
    "Slide P horizontally: ",
    Slider[P](0..100,50,'showticks','filled'=true,'majorticks'=50,'onchange'=ThirdPoint(),'minorticks'=10,'snapticks'=false),
    CheckBox['yPPos'](caption="yP Postive", 'onchange'=ThirdPoint())
  ),
 BoxRow('halign'=left,
        "           P = (",
         TextField['xP']("3",'background'=white,'foreground'= red,'editable'=false,'width'=10),
        ", ",                                  
         TextField['yP']("-5.477",'editable'= false,'background'=white,'foreground'= red,'width'=10),
        ")"
 ),
 BoxRow('halign'=left,
    "Slide Q horizontally: ",
    Slider[Q](0..100,30,'showticks','filled'=true,'majorticks'=50,'onchange'=ThirdPoint(),'minorticks'=10,'snapticks'=false),
    CheckBox['yQPos'](caption="yQ Postive", 'onchange'=ThirdPoint())
  ),
 BoxRow('halign'=left,
        "           Q = (",
         TextField['xQ']("1",'background'=white,'foreground'= magenta,'editable'=false,'width'=10),
        ", ",                                  
         TextField['yQ']("-2.449",'background'=white,'foreground'= magenta,'editable'=false,'width'=10),
        ")"
 ),
 BoxRow('halign'=left,
        "           -R = (",
         TextField['xR']("-1.708",'background'=white,'foreground'= blue,'editable'=false,'width'=10),
        ", ",
        TextField['yR']("1.65",'background'=white,'foreground'= blue,'editable'=false,'width'=10),
        ")")
 ) #box column
) #box layout
) #window
): #maplet

Maplets[Display](ThreePointMaplet);

Addition Maplet

The Third Point property gives us some nice results when we define an operation on two points on an elliptic curve. When we draw a line through P and Q, it intersects the curve at a unique point -R. We can reflect the point -R in the x-axis to get the point R. We say that P+Q=R following this rule.

In the following applet, you can experiment with addition of points on an elliptic curve. You can use the sliders to choose parameters a and b for the elliptic curve, and sliders to choose points P and Q on the curve. The mapelt displays the point P + Q.

You may wish to consider the following:
(1) What do you get if you add P to -P?
(2) How do you adapt the rule to add P to itself?

Warning, `m` is implicitly declared local to procedure `AddPointx`

Warning, `m` is implicitly declared local to procedure `AddPointy`

Doubling Points

To add a point P to itself, we do not have a well-defined secant line. However, a tangent line to the elliptic curve at P will (almost always) intersect the curve at a unique "Second Point" -R. This point is reflected to get R=P+P = 2P.

In this maplet, you can select a variety of points P and see the geometric construction for 2P.
You may wish to consider the following:
(1) Can you find a P for which the tangent line does not intersect the curve at a unique second point? What is 2P in this case?

Warning, `m` is implicitly declared local to procedure `DoublePointx`

Warning, `m` is implicitly declared local to procedure `DoublePointy`

Repeated Addition Maplet

Applications of elliptic curves to cryptography use multiplication of a point P by a scalar k. We can compute kP by adding P to itself repeatedly. While in practise this is an inefficient way to compute kP, for the purposes of learning, scalar multiplication by repeated addition suggests some insight into possible values for kP.

You may wish to consider:

1) How many points are on an elliptic curve?

2) By generating P, 2P, 3P, 4P, ..., can you eventually get all the points on the curve? How many additions would you need to perform to do so?

3) Suppose that 104P = -P. What is the value of 105P? 106P? In this case, can you generate all the points on the elliptic curve?
4) Suppose you want to compute 9P using repeated addition. How many operations (addition or doubling) are needed? Can you determine a sequence of additions/doubling operations that will compute 9P in fewer operations? How could you generalize this into an efficient method for computing kP?

Warning, `m` is implicitly declared local to procedure `AddPointx`

Warning, `m` is implicitly declared local to procedure `AddPointy`