| Download
All published worksheets from http://sagenb.org
Project: sagenb.org published worksheets
Views: 168714Image: ubuntu2004
| b = -1 | b = 0 | b = 1 | |
| a = -2 |  |  |  |
| a = -1 |  |  |  |
| a = 0 |  |  |  |
| a = 1 |  |  |  |
Figure 3.1 Elliptic curves defined by y^2=x^3+ax+b.
Elliptic Curves over the Real Numbers
|
|||||||||||||||||||
Figure 3.2 Play around with different values for a and b and note how the curve changes. You can choose a between -10 and
3, and b between -10 and 10, because this is the range where you can see something happening. Also note that this program
only lets you choose integers for a and b, although real numbers are actually allowed for a curve over the real numbers. This
is because real numbers for a and b would make the output ugly.
3, and b between -10 and 10, because this is the range where you can see something happening. Also note that this program
only lets you choose integers for a and b, although real numbers are actually allowed for a curve over the real numbers. This
is because real numbers for a and b would make the output ugly.
Elliptic Curves over Finite Fields
|
|||||||||||||||||||||||
Figure 3.3 You may choose different finite fields by selecting the parameter p, as well as different elliptic curves by changing
a and b. Observe how the number of points grows with the field size, and how fundamentally different these curves look from
curves over the real numbers defined by the same equations.
a and b. Observe how the number of points grows with the field size, and how fundamentally different these curves look from
curves over the real numbers defined by the same equations.
Point Addition
|
||||||||||||||
Figure 3.4 This graphic visualizes the addition of two points P and Q on a specific elliptic curve. Click on the numbers to see
the process step by step.
the process step by step.
Point Doubling
|
||||||||||||||
Figure 3.5 This graphic visualizes the doubling of a point P on a specific elliptic curve. Click on the numbers to see the
process step by step.
process step by step.
 |
Point Addition for Elliptic Curves over the Rational Numbers
|
|||||||||||||||||||||||||||
Figure 3.7 Try adding some points. You may choose the curve parameters a and b, and the x-coordinates xP and xQ of the
points P and Q that you wish to add (type them in the format 2.5 or 5/2). The program then determines the appropriate
y-coordinate (such that (x,y) solves the curve equation). By default, it always takes the positive value for y. You can tell the
program to use the negative value by checking the appropriate negative yP or negative yQ box. Although we are working
with curves over the rational numbers, not every rational number is a valid x-coordinate (this is only the case if the
corresponding y-coordinate is also rational). The program will inform you in such a case and you will have to choose a
different value.
points P and Q that you wish to add (type them in the format 2.5 or 5/2). The program then determines the appropriate
y-coordinate (such that (x,y) solves the curve equation). By default, it always takes the positive value for y. You can tell the
program to use the negative value by checking the appropriate negative yP or negative yQ box. Although we are working
with curves over the rational numbers, not every rational number is a valid x-coordinate (this is only the case if the
corresponding y-coordinate is also rational). The program will inform you in such a case and you will have to choose a
different value.
Point Addition for Elliptic Curves over Finite Fields
|
|||||||||||||||||||||||||||||||
Figure 3.8 Now try adding some points on curves over finite fields. You may choose the size p of the finite field, the curve
parameters a and b, and the x-coordinates xP and xQ of the points P and Q that you wish to add. Again, not all values for
xP result in a valid y-coordinate. You may try choosing a point from the graph of the curve and entering the value of its
x-coordinate. The program then determines the appropriate y-coordinates (such that (x,y) solves the curve equation). Observe
that this discrete case cannot be visualized as nicely as the continuous case (i.e. curves over the real numbers). Because we
are working with modulo arithmetic where numbers "wrap around" from p-1 to 0, points seem to "jump around" in space,
with the result that straight lines cannot be graphed as such.
parameters a and b, and the x-coordinates xP and xQ of the points P and Q that you wish to add. Again, not all values for
xP result in a valid y-coordinate. You may try choosing a point from the graph of the curve and entering the value of its
x-coordinate. The program then determines the appropriate y-coordinates (such that (x,y) solves the curve equation). Observe
that this discrete case cannot be visualized as nicely as the continuous case (i.e. curves over the real numbers). Because we
are working with modulo arithmetic where numbers "wrap around" from p-1 to 0, points seem to "jump around" in space,
with the result that straight lines cannot be graphed as such.
Double-and-Add Algorithm
|
|||||||||||||||
Figure 3.9 Click through the steps of the algorithm. For clarity, the original point (that it wants to calculate a multiple of) is
denoted P0 and the remembered value of multiples of P0 is denoted P. If you want to change the value of m, click on the gray
%hide above. A window of code will appear. In the second line, change the number 500 to your desired value of m. Do not
change any of the other code. Then hit the keys Shift + Enter. (Unfortunately there is no better way of doing this in the
current version of Sage!)
denoted P0 and the remembered value of multiples of P0 is denoted P. If you want to change the value of m, click on the gray
%hide above. A window of code will appear. In the second line, change the number 500 to your desired value of m. Do not
change any of the other code. Then hit the keys Shift + Enter. (Unfortunately there is no better way of doing this in the
current version of Sage!)
Figure 3.10 Comparison of the three methods of scalar multiplication. Notice that the graph on the right is a logarithmic view,
meaning that the x-axis shows m and not t (the length of m).
meaning that the x-axis shows m and not t (the length of m).