 Application Center - Maplesoft

# Elliptic Curve Arithmetic over the Real Numbers

You can switch back to the summary page by clicking here.

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,...

 > with(plots):

Warning, the name changecoords has been redefined

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

 > #FIRST EXECUTION GROUP - INITIALIZATION restart: with(plots): # Given a y coordinate of a point, returns an appropriate y coordinate to place the point's label LabelYCor := proc(y, ymin,ymax)         local r:         r := abs(ymax - ymin)/20:         return `if`(y >=0,y + r,y-r) end: # Given parameters a and b for the elliptic curve, and x coordinate of a point on the curve, # and a boolean value indicating whether the y coordinate is positive or negative, # returns the y coordinate of the point CurvePoint := proc(a,b,xP,yPPos)     e := x-> evalf(sqrt(x^3+a*x+b)):     if (yPPos = true) then         return e(xP):     else         return -e(xP):     end if: end: # Expects a number P from 0..100. # Returns an x coordinate of a point on the elliptic curve with parameters a and b. xPCor := proc(a,b,P)     local roots:     roots:=fsolve(x^3+a*x+b=0);     # If the curve has more than one root, it has the shape of a closed "circle" and a side piece.     # Inputs of P from 0 to 50 return points on the closed circle.     # Inputs of P from 51 to 100 return points on the side piece.     if (length(roots) 0 and P < 50) then            return roots + (roots-roots)*P/50;         elif (P=50) then            return roots;         elif (P>50) then            return roots + 5*(P-50)/50;         end if:     else         return roots + P/10;     end if: end:

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);

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?

 > #Doubling maplet with(Maplets[Elements]): with(plots): # Given parameter a for the elliptic curve, and x,y coordinate of a point P on the curve, # returns the x coordinate of the point R=2P DoublePointx := proc(a,xP,yP)     local xR:     if (abs(yP) <0.1) then         xR := infinity:     else             m:= (3*xP^2 + a)/(2*yP):             xR:= m^2-2*xP:     end if:     return xR: end: # Given x,y coordinate of a P on the curve, # returns the y coordinate of the point R=2P DoublePointy := proc(a,xP,yP,xR)     local yR:     if (abs(yP) <0.1) then         yR := infinity:     else             m:= (3*xP^2 + a)/(2*yP):             yR := -yP + m*(xP-xR):     end if:     return yR: end: # Given parameters a and b for an elliptic curve, and a number P from 0 to 100, #  chooses a point on the elliptic curve corresponding to the value of P, #  and plots the elliptic curve, P and 2P. eDoublePoint := proc(a,b,xP,yP,xR,yR)     local curve, pointP, textP,  m, pointR, textR, textmR, TangentLine, 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 does not form a group.",color=green):                 display(curve);         else                         if (abs(yP) <0.1) then                         # The roots r of the curve have vertical tangents. When you double such a point, you get the point at infinity.                         # Calculate the viewing rectangle                         xmin := min(-4,xP)-1:                         xmax := max(4,xP)+1:                         ymin := min(-6,yP)-1:                         ymax := max(6,yP)+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="2P is the Point at Infinity.",color=green):                             pointP := pointplot({[xP,yP]},color=red):                         textP :=textplot({[xP,LabelYCor(yP,ymin,ymax),"P"]},font=[TIMES,BOLDITALIC,12],color=red):                         TangentLine := implicitplot({x=xP},x=xmin..xmax,y=ymin..ymax,grid=[GridSize,GridSize], color=black):                             display(curve,pointP, textP,TangentLine);                                           else                         # 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, 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):                         pointR := pointplot({[xR,yR],[xR,-yR]},color=blue):                         textR := textplot({[xR,LabelYCor(yR,ymin,ymax),"2P"]},font=[TIMES,BOLDITALIC,12],color = blue):                         textmR := textplot({[xR,LabelYCor(-yR,ymin,ymax),"-R"]},font=[TIMES,BOLDITALIC,12],color=gray):                         TangentLine := implicitplot({y-yP=m*(x-xP)},x=xmin..xmax,y=ymin..ymax,grid=[GridSize,GridSize], color=black):                         ReflectionLine := implicitplot({x=xR},x=xmin..xmax,y=ymin..ymax,grid=[GridSize,GridSize], color=blue, linestyle=DOT):                                                      display(curve,pointP, textP,TangentLine, ReflectionLine,pointR,textR,textmR);                 end if:         end if;     catch:         textP :=textplot({[1,1,xP]},font=[TIMES,ITALIC,12],color=plum):         curve := implicitplot({y^2=x^3+a*x+b},x=-6..6,y=-6..6,grid=[GridSize,GridSize],color=green):         display(curve);     end try; end: Double:=()->Action(         Evaluate('xP' = 'xPCor(a,b,P)'),         Evaluate('yP' = 'CurvePoint(a,b,xP,yPPos)'),         Evaluate('xR' = 'DoublePointx(a,xP,yP)'),         Evaluate('yR' = 'DoublePointy(a,xP,yP,xR)'),         Evaluate('PL1' = 'eDoublePoint(a,b,xP,yP,xR,yR)'),         Evaluate('eq'= 'y^2=x^3+a*x+b') ): DoubleMaplet := Maplet(  Window('title'= "Elliptic Curves: Doubling a point P",  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'=Double(),'minorticks'=1,'snapticks'=false), "b: ", Slider[b](-10..10, 6,'showticks','filled'=true,'majorticks'=5,'onchange'=Double(),'snapticks'=false,'minorticks'=1)),  BoxRow(Plotter['PL1'](eDoublePoint(-1,6,3,-5.477,-0.3666,-2.513))),   BoxRow('halign'=left,     "Slide P horizontally: ",     Slider[P](0..100,50,'showticks','filled'=true,'majorticks'=50,'onchange'=Double(),'minorticks'=10,'snapticks'=false),     CheckBox['yPPos'](caption="yP Postive", 'onchange'=Double())   ),  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,         "2P = R= (",          TextField['xR']("-0.3666",'background'=white,'foreground'=blue,'editable'=false,'width'=10),         ", ",         TextField['yR']("-2.513",'editable'=false,'background'=white,'foreground'=blue,'width'=10),         ")")  ) #box column ) #box layout ) #window ): #maplet Maplets[Display](DoubleMaplet);

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

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

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?