Cryptography Reference
In-Depth Information
(
Q
)
Exercise 11.6
We have seen an example of a rational elliptic curve such that
E
(
Q
)
has no points of order 2 and an example in which
E
has just one point of order
2. Give an example in which
E
has three points of order 2 and show that these
three examples cover all possible cases.
(
Q
)
11.2 Elliptic Curves Over Finite Fields
The elliptic curves of cryptographic interest are mainly elliptic curves over finite
fields and we will devote special attention to the case of a prime field
F
p
.
11.2.1 Some Small Examples
When the field is finite the elliptic curve defines a finite group and in order to obtain
a first impression about this group we may consider a few examples over a small
field. In general, to compute all the points of an elliptic curve
E
(
F
p
)
given by the
Weierstrass equation
y
2
x
3
=
+
+
∈ F
p
,
ax
b
, we have to check first, for each
x
whether
x
3
+
+
ax
b
is or not a quadratic residue modulo
p
(which can be efficiently
determined by computing the Legendre symbol
x
3
). As we have seen, half
+
ax
+
b
p
F
p
of the elements of
are quadratic residues and each of them has
just two square roots, while the quadratic non-residues do not have a square root.
= F
p
−{
0
}
Thus, each time that
x
3
+
ax
+
b
p
∈ F
p
, we obtain two square roots
=
1forsome
x
and when
x
3
±
y
and two points
(
x
,
±
y
)
∈
E
(
F
p
)
+
ax
+
b
=
0 we obtain the
(when
x
3
+
ax
+
b
point
(
x
,
0
)
∈
E
(
F
p
)
=−
1, no point is obtained). These points,
p
together with the point at infinity
O
, form the group
E
(
F
p
)
. Note that the order
|
will be even precisely when there is a point of order 2 which, as we have
seen, is equivalent to the polynomial
x
3
E
(
F
p
)
|
+
ax
+
b
having a zero in
F
p
. Thus the group
has odd order if and only if this polynomial is irreducible in
F
p
[
x
]
(which means
that it has no zeros in
F
p
). In the following we will refer to
|
E
(
F
p
)
|
as the order
of the curve
E
over
is frequently called the cardinality of the curve or,
simply, the number of points of the curve, but we will use the group-theoretic term
order for brevity.
The smallest prime field that satisfies our requirement of having characteristic
greater than 3 is
F
p
.
|
E
(
F
p
)
|
F
5
= Z
5
and this field is small enough to allow us to do the
preceding computation by hand. Let us look at a couple of examples.
Examples 11.1
Consider first the elliptic curve
E
defined by the equation
y
2
x
3
=
+
2
x
F
5
(note that 4
a
3
27
b
2
mod 5
over
+
=
2
=
0 and hence the equation defines an
F
5
,
x
3
elliptic curve). Across all values of
x
on
+
2
x
is either 2 or 3 which are both
