Cryptography Reference
In-Depth Information
We see that the curve has symmetry about a horizontal axis but there are no points
below the x -axis. The reason is that we are using the integers in the interval
[
,
]
0
p
1
to represent the elements of
F p but if we use instead the “least absolute residue”
then the x -axis would become the axis of symmetry of the curve. To obtain this
representation in Maple we just have to replace the list ep by mods ~ (ep,2017) .
Exercise 11.10 Modify the procedure EllipticPoints so that it accepts as an
additional parameter an interval
1, and computes
all the points in the elliptic curve whose x -coordinate belongs to this interval. Make
this parameter optional and such that if no argument is passed to it then the procedure
just computes the set of all points on the elliptic curve.
[
x 0 ,
x 1 ]
, where 0
x 0
x 1
p
The method used to generate the points also gives a naive way to count their
number without having to explicitly compute them. It is based on the following easy
result:
F p defined by the equation y 2
Proposition 11.2
If E is the elliptic curve over
=
0 x 3
.
+ p 1
x
x 3
+
ax
+
b
+
ax
+
b, then
|
E
( F p ) |=
p
+
1
=
p
Proof As we have seen, for a given element x 0 ∈ F p , the number of points on the
curve with x -coordinate equal to x 0 is equal to 2, 0 or 1 according to whether the
Legendre symbol x 0 + ax 0 + b
p
takes the value
+
1,
1, or 0, respectively. Thus we
x 0 + ax 0 + b
p
. Adding these terms over the p
see that this number is precisely 1
+
elements of
F p and adding 1 for the point at infinity, we obtain the stated formula.
Proposition 11.2 provides an algorithm for computing the number of points on
an elliptic curve but the number of Legendre symbols to be computed is O
and
hence the running time is exponential in the size of p . As a consequence, this naive
algorithm is only useful for curves over small fields but we will use it to get an idea
of the distribution of orders of elliptic curves over prime fields. The Maple function
below is a straightforward implementation of the algorithm:
(
p
)
> EllipticGroupOrder := proc(E::list(integer))
local a, b, p, x;
a := E[1];
b := E[2];
p := E[3];
1+p+add(numtheory:-legendre(xˆ3+a*x+b, p), x=0..p-1)
end proc:
For example:
> EllipticGroupOrder(EllipticCurve(4, 0, 5));
8
 
Search WWH ::




Custom Search