Cryptography Reference
In-Depth Information
6. V
2
i
+
1
=
V
i
V
i
+
1
−
V
1
.
V
1
V
i
−
7. V
2
i
+
1
=
V
i
V
i
−
1
−
V
1
.
8. V
i
+
j
=
V
i
V
j
−
V
i
−
j
.
=
g
q
=
v
1
+
=
+
=
(
v
1
+
+
(
v
1
+
−
−
Proof
Let
g
w
1
θ
. Then Tr
F
q
2
/
F
q
(
g
)
g
g
w
1
θ
)
w
1
(
θ
Aw
1
. S
i
milarly,
g
0
A
))
=
2
v
1
−
=
1 and the first statement is proven. The second statement
follows from
g
−
1
=
g
. Statements 3 to 6 are all special cases of statement 8, which follows
from the equation
g
i
+
j
g
i
+
j
(
g
i
g
i
)(
g
j
g
j
)
g
j
g
j
(
g
i
−
j
g
i
−
j
)
.
V
i
+
j
=
+
=
+
+
−
+
(An alternative proof of Statement 3 is to use the fact that
g
satisfies
g
2
=
V
1
g
−
1.)
Statement 7 then follows from 3 and 6.
(
g
i
g
i
)
/
(
g
Exercise 6.3.15
Define
U
i
=
−
−
g
). Prove that
U
i
+
1
=
Tr
F
q
2
/
F
q
(
g
)
U
i
−
U
i
−
1
,
U
2
i
=
V
i
U
i
,
U
i
+
j
=
U
i
U
j
+
1
−
U
i
−
1
U
j
.
Definition 6.3.16
Denote by
G
q,
2
/
σ
the set of equivalence classes of
G
q,
2
under the
g
q
g
−
1
. Denote the class of
g
g,g
q
equivalence relation
g
≡
σ
(
g
)
=
=
∈
G
q,
2
by [
g
]
={
}
.
=
Tr
F
q
2
/
F
q
(
g
q
) and so a class [
g
] can be iden-
The main observation is that Tr
F
q
2
/
F
q
(
g
)
tified with the value
V
=
Tr
F
q
2
/
F
q
(
g
). This motivates Definition
6.3.18
. When
q
is odd,
the classes [1] and [
2 respectively; apart from these
cases, the other possible values for
V
are those for which the polynomial
x
2
−
1] correspond to
V
=
2 and
V
=−
−
Vx
+
1is
irreducible over
F
q
.
Tr
F
q
2
/
F
q
(
g
)for
g,g
∈
G
q,
2
then
g
∈{
g,g
q
Exercise 6.3.17
Prove that if Tr
F
q
2
/
F
q
(
g
)
=
}
.
Hence, show that when
q
is odd there are 2
+
(
q
−
1)
/
2 values for Tr
F
q
2
/
F
q
(
g
) over
g
∈
G
q,
2
.
∈
∈ N
The set
G
q,
2
/
σ
is not a group; however, for a class [
g
]
G
q,
2
/
σ
and
n
one can
define [
g
]
n
to be [
g
n
].
Definition 6.3.18
Let
G
q,
2
={
G
q,
2
Tr
F
q
2
/
F
q
(
g
):
g
∈
G
q,
2
}
.For
V
∈
and
n
∈ N
define
Tr
F
q
2
/
F
q
(
g
n
) for any
g
[
n
]
V
Tr
F
q
2
/
F
q
(
g
).
It follows that we may treat the set
G
q,
2
as an algebraic group quotient. One method to
efficiently compute [
n
]
V
for
n
=
∈
G
q,
2
such that
V
=
∈ F
q
2
of
x
2
∈ N
is to take a root
g
−
Vx
+
1
=
0, compute
g
n
in
F
q
2
using the square-and-multiply method and then compute Tr
F
q
2
/
F
q
(
g
n
). However,
we want to be able to compute [
n
]
V
directly using an analogue of the square-and-multiply
method.
5
Lemma
6.3.14
shows that, although
V
2
n
is determined by
V
n
and
n
,
V
n
+
1
is not
determined by
V
n
alone. Hence, it is necessary to develop an algorithm that works on a
pair (
V
n
,V
n
−
1
) of consecutive values. Such algorithms are known as
ladder methods
.One
starts the ladder computation with (
V
1
,V
0
)
=
(
V,
2).
5
In practice, it is often more efficient to use other processes instead of the traditional square-and-multiply method. We refer to
Chapter 3 of [
520
] for more details.
