# Metrics on the Sets of Nonsupersingular Elliptic Curves in Simplified Weierstrass Form over Finite Fields of Characteristic Two

Authors: Keisuke Hakuta
Journal: International Journal of Mathematics and Mathematical Sciences
 (2015)

---

## Abstract

Elliptic curves have a wide variety of applications in computational number theory such as elliptic curve cryptography, pairing based cryptography, primality tests, and integer factorization. Mishra and Gupta (2008) have found an interesting property of the sets of elliptic curves in simplified Weierstrass form (or short Weierstrass form) over prime fields. The property is that one can induce metrics on the sets of elliptic curves in simplified Weierstrass form over prime fields of characteristic greater than three. Later, Vetro (2011) has found some other metrics on the sets of elliptic curves in simplified Weierstrass form over prime fields of characteristic greater than three. However, to our knowledge, no analogous result is known in the characteristic two case. In this paper, we will prove that one can induce metrics on the sets of nonsupersingular elliptic curves in simplified Weierstrass form over finite fields of characteristic two.


---

## Body

## 1. Introduction

Elliptic curves have been studied by number theorists for a very long time. Nowadays, elliptic curves have been the focus of much attention due to not only the theoretical aspects but also the practical aspects in computational number theory. In particular, elliptic curves have a wide variety of applications in computational number theory such as elliptic curve cryptography [1, 2], pairing based cryptography [3, 4], primality tests [5, 6], and integer factorization [7, 8].Mishra and Gupta in [9] have found an interesting property of the sets of elliptic curves in simplified Weierstrass form (or short Weierstrass form) over prime fields of characteristic greater than three. The property is that one can induce metrics on the sets of elliptic curves in simplified Weierstrass form over prime fields of characteristic greater than three. Later, Vetro in [10] has found some other metrics on the sets of elliptic curves in simplified Weierstrass form over prime fields of characteristic greater than three. They have proposed potential applications of the metrics to the protection of side channel attacks [11]. However, to our knowledge, no analogous result is known in the characteristic two case. In this direction, it seems mathematically natural to explore a methodology for constructing metrics on (sub)sets of elliptic curves over finite fields of characteristic two whether there is a cryptographic application or not.The motivation of this work is to studythe characteristic two case. We will prove that one can induce metrics on the sets of nonsupersingular elliptic curves in simplified Weierstrass form over finite fields of characteristic two.The rest of this paper is organized as follows. In Section2, we recall some basic facts that will be used throughout the paper. In Section 3, we give metrics on the sets of nonsupersingular elliptic curves in simplified Weierstrass form over finite fields of characteristic two. Section 4 concludes the paper.


## 2. Mathematical Preliminaries

In this section we fix our notation and recall some basic facts that will be used throughout the paper. For more details, we refer the reader to [12, Section 3.3], [13, Appendix A].LetK be a field. For any field K, we denote by p
=
c
h
a
r
(
K
) the characteristic of the field K. We use the symbols Z, R, and F
q to represent the integers, real numbers, and a finite field with q elements, where q
=
p
r (r
≥
1), p
=
c
h
a
r
(
F
q
). For a finite set S, we denote the cardinality of S by ♯
S.LetE
/
K
:
y
2
+
a
1
x
y
+
a
3
y
=
x
3
+
a
2
x
2
+
a
4
x
+
a
6 be an algebraic curve over K. We set(1)
d
2
=
a
1
2
+
4
a
2
,
d
4
=
2
a
4
+
a
1
a
3
,
d
6
=
a
3
2
+
4
a
6
,
d
8
=
a
1
2
a
6
+
4
a
2
a
6
-
a
1
a
3
a
4
+
a
2
a
3
2
-
a
4
2
,
c
4
=
d
2
2
-
24
d
4
,
Δ
=
-
d
2
2
d
8
-
8
d
4
3
-
27
d
6
2
+
9
d
2
d
4
d
6
,
j
E
=
c
4
3
Δ
.The next theorem provides a necessary and sufficient condition that E
/
K is an elliptic curve.Theorem 1 (see [12, Theorem 2.4]).
Eis an elliptic curve; that is, the Weierstrass equation is nonsingular, if and only if Δ
≠
0.Two elliptic curvesE
1 and E
2 are called isomorphic if there exist morphisms (as algebraic varieties) from E
1 to E
2 and from E
2 to E
1 which are inverses of each other. The following theorems (Theorems 2 and 3) tell us when two elliptic curves are isomorphic.Theorem 2 (see [12, Theorem 2.5]).
If two elliptic curvesE
1
/
K and E
2
/
K are isomorphic over K, then j
(
E
1
)
=
j
(
E
2
). The converse is also true if K is an algebraically closed field.Theorem 3 (see [12, Theorem 2.1]).
Two elliptic curvesE
1
/
K and E
2
/
K given by the equations(2)
E
1
:
y
2
+
a
1
x
y
+
a
3
y
=
x
3
+
a
2
x
2
+
a
4
x
+
a
6
,
E
2
:
y
2
+
a
¯
1
x
y
+
a
¯
3
y
=
x
3
+
a
¯
2
x
2
+
a
¯
4
x
+
a
¯
6are isomorphic over K (or K-isomorphic), denoted by E
1
/
K
≅
E
2
/
K, if and only if there exists u
,
r
,
s
,
t
∈
K, u
≠
0, such that the change of variables(3)
x
,
y
⟼
u
2
x
+
r
,
u
3
y
+
u
2
s
x
+
ttransforms equation E
1 to equation E
2. The relationship of isomorphism is an equivalence relation.Theorem4 is the famous Hasse bound for the number of rational points on elliptic curves over finite fields.Theorem 4 (Hasse).
Let♯
E
(
F
q
)
=
q
+
1
-
t. Then |
t
|
≤
2
q.The elliptic curveE
/
F
q is calledsupersingular if p divides t. Otherwise, the curve E
/
F
q is callednonsupersingular (orordinary). It is well-known that if p
=
2 or p
=
3, then E is supersingular if and only if j
(
E
)
=
0. In other words, if p
=
2 or p
=
3, E is nonsupersingular if and only if j
(
E
)
≠
0. Remark that if E
/
K
:
y
2
+
a
¯
1
x
y
+
a
¯
3
y
=
x
3
+
a
¯
2
x
2
+
a
¯
4
x
+
a
¯
6 is an elliptic curve with c
h
a
r
(
K
)
=
2 and j
(
E
)
≠
0, then the admissible change of variables(4)
x
,
y
⟼
a
¯
1
2
x
+
a
¯
3
a
¯
1
,
a
¯
1
3
y
+
a
¯
1
2
a
¯
4
+
a
¯
3
2
a
¯
1
3transforms E to the nonsupersingular elliptic curve(5)
E
′
/
K
:
y
2
+
x
y
=
x
3
+
a
2
x
2
+
a
6
.An elliptic curve of form (5) is calledsimplified Weierstrass form (orshort Weierstrass form). Let E
1
/
F
2
m
,
E
2
/
F
2
m
(6)
E
1
:
y
2
+
x
y
=
x
3
+
a
2
x
2
+
a
6
a
6
≠
0
,
E
2
:
y
2
+
x
y
=
x
3
+
a
¯
2
x
2
+
a
¯
6
a
¯
6
≠
0be nonsupersingular elliptic curves over F
2
m in simplified Weierstrass form. If E
1
/
F
2
m
≅
E
2
/
F
2
m, then we have a
6
=
a
¯
6 and the isomorphism is given by(7)
ϕ
s
:
E
1
⟶
E
2
,
x
,
y
⟼
x
,
y
+
s
x
,where s is an element in F
2
m and satisfies the equation(8)
s
2
+
s
=
a
2
+
a
¯
2(see [12, Section 3.3]).Remark that ifs
1 is a solution of (8) then s
2
≔
s
1
+
1 is the other solution. Furthermore, ϕ
s is an automorphism if and only if s
∈
{
0,1
} ([13, Appendix A, Proposition 1.2]).


## 3. Metrics

In this section we assume thatK
=
F
2
m for m
≥
2. We consider the set of nonsupersingular elliptic curves over F
2
m in simplified Weierstrass form; namely,(9)
E
m
≔
E
/
F
2
m
:  elliptic curve
∣
E
is of the form
5
.Throughout this section, we assume that E
i
/
F
2
m
∈
E
(
m
) are elliptic curves for i
=
1,2
,
3. In addition, we denote(10)
ϕ
s
:
E
1
⟶
E
2
,
x
,
y
⟼
x
,
y
+
s
x
,
ϕ
t
:
E
2
⟶
E
3
,
x
,
y
⟼
x
,
y
+
t
x
,
ϕ
u
:
E
1
⟶
E
3
,
x
,
y
⟼
x
,
y
+
u
x
,if E
1
/
F
2
m
≅
E
2
/
F
2
m, E
2
/
F
2
m
≅
E
3
/
F
2
m, and E
1
/
F
2
m
≅
E
3
/
F
2
m, respectively. Let B
~ be the set of all basis of a linear space F
2
m over F
2. We put(11)
B
≔
v
=
v
1
,
…
,
v
m
∈
B
~
∣
there exists
j
∈
1
,
…
,
m
such that
v
j
=
1
,where 1
∈
F
2
m is the multiplicative identity element. Note that the set B is a nonempty finite set because a polynomial basis belongs to the set B. We choose a basis v
=
〈
v
1
,
…
,
v
m
〉
∈
B and fixed it. Then there exists j
0
∈
{
1
,
…
,
m
} such that v
j
0
=
1. Let(12)
f
j
0
:
F
2
m
⟶
F
2
m
-
1
⟒
⟒
x
=
∑
i
=
1
m
x
i
v
i
⟼
f
j
0
x
=
x
^
j
0
=
x
1
,
…
,
x
j
0
-
1
,
x
j
0
+
1
,
…
,
x
m denote the surjective F
2-linear map, where x
i
∈
F
2 (1
≤
i
≤
m). For any x
=
∑
i
=
1
m
x
i
v
i
∈
F
2
m (x
i
∈
F
2), we write(13)
w
t
f
j
0
x
=
w
t
x
^
j
0
≔
♯
i
∈
1
,
…
,
m
∣
i
≠
j
0
,
x
i
≠
0
. Note that, for all x
∈
F
2
m, we always have w
t
f
j
0
x
≤
m
-
1. We put s
=
∑
i
=
1
m
s
i
v
i
∈
F
2
m (s
i
∈
F
2), t
=
∑
i
=
1
m
t
i
v
i
∈
F
2
m (t
i
∈
F
2), and u
=
∑
i
=
1
m
u
i
v
i
∈
F
2
m (u
i
∈
F
2) for the isomorphisms of form (10).Now we define the functiond
v
(
m
)
:
E
(
m
)
×
E
(
m
)
→
R as follows: (14)
d
v
m
:
E
m
×
E
m
⟶
R
⟒
⟒
E
1
,
E
2
⟼
w
t
f
j
0
s
if
E
1
/
F
2
m
≅
E
2
/
F
2
m
,
E
1
,
E
2
⟼
m
otherwise
.Remark that the function d
v
(
m
) is well-defined because, for two solutions s
1, s
2 (s
2
=
s
1
+
1) of (8), we have w
t
f
j
0
s
1
=
w
t
f
j
0
s
2. Namely, the function d
v
(
m
)
does not depend on the choice of isomorphisms.We are ready to state and prove the main result of this paper, namely, Theorem5, which states that the set of nonsupersingular elliptic curves over F
2
m in simplified Weierstrass form is a metric space under the metric d
v
(
m
).Theorem 5 (metric onE
(
m
)).
(
E
(
m
)
,
d
v
(
m
)
) is a metric space.Proof.
We prove the nonnegativity, the nondegeneracy, the symmetry, and the triangular inequality.(1) Nonnegativity. By the definition of the function d
v
(
m
), we have d
v
(
m
)
(
E
1
,
E
2
)
≥
0 for all E
1
,
E
2
∈
E
(
m
).(2) Nondegeneracy. Suppose that d
v
(
m
)
(
E
1
,
E
2
)
=
0. Since m
≥
2, we must have w
t
f
j
0
s
=
w
t
(
s
^
j
0
)
=
0. This implies that s
i
=
0 for all i
≠
j
0. Remember that s
i
∈
F
2
=
{
0,1
}. Setting s
j
0
=
0 (resp., s
j
0
=
1) yields s
=
0 (resp., s
=
1). When s
=
0 or s
=
1, the isomorphism of form (10) is an automorphism. Thus, E
1
=
E
2. Conversely, if E
1
=
E
2, then the isomorphism of form (10) is an automorphism. It then follows that s
=
0,1. Hence s
i
=
0 for all i
≠
j
0 and therefore d
v
(
m
)
(
E
1
,
E
2
)
=
w
t
f
j
0
s
=
0.(3) Symmetry. If E
1
/
F
2
m
≇
E
2
/
F
2
m, then d
v
(
m
)
(
E
1
,
E
2
)
=
d
v
(
m
)
(
E
2
,
E
1
)
=
m. Otherwise, we define(15)
ψ
:
E
2
⟶
E
1
,
x
,
y
⟼
x
,
y
+
s
x
.One can easily check that ψ is an isomorphism. Thus d
v
(
m
)
(
E
1
,
E
2
)
=
d
v
(
m
)
(
E
2
,
E
1
)
=
w
t
(
s
^
j
0
).(4) Triangular Inequality. Let E
1
,
E
2
,
E
3
∈
E
(
m
). We claim that(16)
d
v
m
E
1
,
E
3
≤
d
v
m
E
1
,
E
2
+
d
v
m
E
2
,
E
3
.There are two cases to consider. Namely, E
1
/
F
2
m
≇
E
3
/
F
2
m and E
1
/
F
2
m
≅
E
3
/
F
2
m.Case 1 (E
1
/
F
2
m
≇
E
3
/
F
2
m). In this case, we have d
v
(
m
)
(
E
1
,
E
3
)
=
m. If follows immediately from E
1
/
F
2
m
≇
E
3
/
F
2
m that E
1
/
F
2
m
≇
E
2
/
F
2
m or E
2
/
F
2
m
≇
E
3
/
F
2
m. Then d
v
(
m
)
(
E
1
,
E
2
)
=
m or d
v
(
m
)
(
E
2
,
E
3
)
=
m. This shows that d
v
(
m
)
(
E
1
,
E
3
)
≤
d
v
(
m
)
(
E
1
,
E
2
)
+
d
v
(
m
)
(
E
2
,
E
3
) as claimed.Case 2 (E
1
/
F
2
m
≅
E
3
/
F
2
m). There are two possibilities: E
1
/
F
2
m
≇
E
2
/
F
2
m and E
1
/
F
2
m
≅
E
2
/
F
2
m. The former case gives d
v
(
m
)
(
E
1
,
E
2
)
=
m, which shows that d
v
(
m
)
(
E
1
,
E
3
)
≤
d
v
(
m
)
(
E
1
,
E
2
)
≤
d
v
(
m
)
(
E
1
,
E
2
)
+
d
v
(
m
)
(
E
2
,
E
3
) (or, more precisely, d
v
(
m
)
(
E
1
,
E
2
)
<
d
v
(
m
)
(
E
1
,
E
2
)
+
d
v
(
m
)
(
E
2
,
E
3
) since E
2
/
F
2
m
≇
E
3
/
F
2
m). In the latter case, we have ϕ
u
=
ϕ
t
∘
ϕ
s. This yields that d
v
(
m
)
(
E
1
,
E
2
)
=
w
t
f
j
0
s, d
v
(
m
)
(
E
2
,
E
3
)
=
w
t
f
j
0
t, and d
v
(
m
)
(
E
1
,
E
3
)
=
w
t
f
j
0
u
=
w
t
f
j
0
s
+
t, respectively. Since |
s
i
+
t
i
|
≤
|
s
i
|
+
|
t
i
| for all i
∈
{
1
,
…
,
m
}, i
≠
j
0, we obtain(17)
w
t
f
j
0
u
=
w
t
f
j
0
s
+
t
≤
w
t
f
j
0
s
+
w
t
f
j
0
t
,where |
s
i
| (resp., |
t
i
|) is equal to 1 when s
i
=
1 (resp., t
i
=
1) and otherwise |
s
i
| (resp., |
t
i
|) is equal to 0. Hence we have d
v
(
m
)
(
E
1
,
E
3
)
≤
d
v
(
m
)
(
E
1
,
E
2
)
+
d
v
(
m
)
(
E
2
,
E
3
). This completes the proof.Remark 6.
The main observation of Theorem5 is that the isomorphism of form (10) is an automorphism if and only if s
∈
{
0,1
}. By omitting the j
0th entry of s and by summing up the number of nonzero s
i with 1
≤
i
≤
m and i
≠
j
0, one can construct a metric on E
(
m
). In order to omit the j
0th entry, we use a basis v which is belonging to the set B. The nonnegativity and the symmetry for d
v
(
m
) are obvious. The nondegeneracy for d
v
(
m
) is followed by the omission of j
0th entry. The triangular inequality for the Hamming distance implies the triangular inequality for d
v
(
m
).In the definition ofd
v
(
m
), we put d
v
(
m
)
(
E
1
,
E
2
)
=
m when E
1
/
F
2
m
≇
E
2
/
F
2
m. However, the value m does not have any special meanings, and one can use any other positive integer greater than or equal to m in order to define different metrics on E
(
m
).Corollary 7 (other metrics onE
(
m
)).
(1) For any integern
∈
Z greater than or equal to m, define the function d
v
(
n
)
:
E
(
m
)
×
E
(
m
)
→
R as follows: (18)
d
v
n
:
E
m
×
E
m
⟶
R
⟒
⟒
E
1
,
E
2
⟼
w
t
f
j
0
s
i
f
E
1
/
F
2
m
≅
E
2
/
F
2
m
,
E
1
,
E
2
⟼
n
o
t
h
e
r
w
i
s
e
.Then (
E
(
m
)
,
d
v
(
n
)
) is a metric space.
(2) We define the functiond
v
(
∞
)
:
E
(
m
)
×
E
(
m
)
→
R
∪
{
∞
} as follows: (19)
d
v
∞
:
E
m
×
E
m
⟶
R
∪
∞
⟒
⟒
E
1
,
E
2
⟼
w
t
f
j
0
s
i
f
E
1
/
F
2
m
≅
E
2
/
F
2
m
,
E
1
,
E
2
⟼
∞
o
t
h
e
r
w
i
s
e
.Then (
E
(
m
)
,
d
v
(
∞
)
) is also a metric space.
(3) Set(20)
N
m
≔
m
,
m
+
1
,
m
+
2
,
…
∪
∞
.We choose a subset S
⊆
B. Since B is a finite set, the subset S is also a finite set. For each v
∈
S, we take n
v
∈
N
m. Then the function(21)
∑
v
∈
S
d
v
n
v
:
E
m
×
E
m
⟶
R
∪
∞
,
E
1
,
E
2
⟼
∑
v
∈
S
d
v
n
v
E
1
,
E
2 is also a metric on E
(
m
).
(4) We putR
>
0
≔
c
∈
R
∣
c
>
0. For each v
∈
S, we take c
v
(
n
v
)
∈
R
>
0
. Then as in (3), we can define the metric(22)
∑
v
∈
S
c
v
n
v
d
v
n
v
:
E
m
×
E
m
⟶
R
∪
∞
,
E
1
,
E
2
⟼
∑
v
∈
S
c
v
n
v
d
v
n
v
E
1
,
E
2 on E
(
m
).Proof.
The proofs are very similar to the proof of Theorem5; thus we omit them.Remark 8 (topological properties of a metric spaceE
(
m
)).
We recall that a metric space gives rise to a topology. Here, we make sure of the properties of the topology onE
(
m
) induced by a metric. Given a metric space (
E
(
m
)
,
d
), let O
d be the topology on E
(
m
) induced by the metric d. Note that the facts shown belowdo not depend on the metric d. A metric space is a Hausdorff space [14, p. 110, Proposition 11.5]. A finite subset of a topological space is compact [14, p. 128, Example 13.8(a)]. These two facts indicate that E
(
m
)
,
O
d is a compact Hausdorff space. If a finite space is Hausdorff then its topology is discrete [14, p. 111, Exercise 11.2(b)]. Therefore O
d is discrete, and hence E
(
m
)
,
O
d is totally disconnected. Any finite metric space is compact, therefore E
(
m
)
,
O
d is a complete metric space.


## 4. Conclusion

In this paper, we have defined some metrics on the sets of nonsupersingular elliptic curves in simplified Weierstrass form over finite fields of characteristic two. In order to derive analogous results for the case ofsupersingular elliptic curves of characteristic two and for the case ofelliptic curves of characteristic three, some deep observation on the properties of elliptic curves over finite fields will be needed.



---

*Source: 597849-2015-12-28.xml*