Cryptography Reference
In-Depth Information
Theorem 6.10.
Given a finite field
K
of characteristic p
>
3
and given a
,
b
∈
K
such
that
4
a
3
27
b
2
+
=
0
, we let E
a
,
b
be the elliptic curve defined in Def. 6.8. The twist of
K
∗
which is not a quadratic residue. We have
E
a
,
b
is E
au
2
bu
3
for u
∈
,
#
E
a
,
b
+
#
E
au
2
=
2#
K
+
2
.
,
bu
3
Proof.
For any
x
∈
K
, we notice that
either
x
3
b
is a nonzero quadratic residue, or and
u
3
(
x
3
+
ax
+
+
ax
+
b
)isnot
a quadratic residue, or
x
3
b
is not a quadratic residue and
u
3
(
x
3
+
ax
+
+
ax
+
b
) is a nonzero
quadratic residue, or
x
3
u
3
(
x
3
+
ax
+
b
=
+
ax
+
b
)
=
0.
Let
f
(
x
) be the number of affine points on
E
a
,
b
(i.e. all points except
O
). When
x
3
2. When
x
3
+
ax
+
b
is a nonzero quadratic residue, then
f
(
x
)
=
+
ax
+
b
is not a
0. When
x
3
quadratic residue, then
f
(
x
)
=
+
ax
+
b
=
0, then
f
(
x
)
=
1. Let
g
(
x
)be
the number of points on
E
au
2
,
bu
3
which can be written (
ux
,
y
). We notice that
g
(
x
)is
respectively 0, 2, and 1 in the three cases. Therefore
f
(
x
)
2 for all
x
. Since
this counts all affine points on
E
a
,
b
and
E
au
2
,
bu
3
, we obtain the result.
+
g
(
x
)
=
Note that since we have a group law, we can define
mP
for any integer
m
and any
point
P
and compute
mP
by the square-and-multiply algorithms which were defined
(with multiplicative notations) in Figs. 6.5 and 6.6.
6.5.2
Characteristic Two
Finite fields of characteristic two are important in practice. For completeness we provide
here the definitions and properties related to elliptic curves over these fields.
Let us first recall that given a finite field
K
of cardinality 2
m
we can define the trace
Tr
2
m
2
function by
,
m
−
1
x
2
i
Tr
2
m
2
(
x
)
=
,
i
=
0
which is a linear form of
K
over GF(2).
K
∗
and
Definition 6.11.
Given a finite field
K
of characteristic two and given a
6
∈
a
2
∈{
0
,γ
}
with
γ
such that
Tr
#
K
,
2
(
γ
)
=
1
,welet
K
2
;
y
2
x
3
a
2
x
2
E
a
2
,
a
6
={
O
}∪{
(
x
,
y
)
∈
+
xy
=
+
+
a
6
}
Search WWH ::
Custom Search