Cryptography Reference
In-Depth Information
Definition 6.1.6
Let
n
∈ N
and
q
a prime power. Define the
cyclotomic subgroup
G
q,n
to
F
q
n
of order
n
(
q
).
be the subgroup of
The subgroups
G
q,n
are of interest as most elements of
G
q,n
do not lie in any subfield
F
q
n
from
the point of view of the DLP. Note that
G
q,n
is trivially an algebraic group, by virtue of
being a subgroup of the algebraic group
of
F
q
n
(see Corollary
6.2.3
below). In other words,
G
q,n
is the “hardest part” of
F
q
n
F
q
n
) (see Example
5.1.4
). The goal of
this subject area is to develop compact representations for the groups
G
q,n
and efficient
methods to compute with them.
The two most important cases are
G
q,
2
, which is the subgroup of
=
G
m
(
F
q
2
of order
q
+
1, and
F
q
6
of order
q
2
G
q,
6
, which is the subgroup of
−
q
+
1. We give compact representations
of these groups in Sections
6.3
and
6.4
.
6.2 Algebraic tori
Algebraic tori are a classical object in algebraic geometry and their relevance to cryptogra-
phy was first explained by Rubin and Silverberg [
452
]. An excellent survey of this area is
[
453
].
Recall from Theorem
5.7.7
that the Weil restriction of scalars of
1
A
with respect to
n
.Let
n>
1 and let
f
:
n
(
F
q
n
/
F
q
is
A
A
F
q
)
→ F
q
n
be a bijective
F
q
-linear function (e.g.,
F
q
n
is a vector space of dimension
n
over
F
q
). For any
corresponding to the fact that
=
n/d
−
1
i
=
0
g
q
di
. The equation N
F
q
n
/
F
q
d
(
f
(
x
1
,...,x
n
))
|
=
d
n
define the norm N
F
q
n
/
F
q
d
(
g
)
1
defines an algebraic set in
A
n
.
Definition 6.2.1
The
algebraic torus
2
T
n
is the algebraic set
n
.
V
(
{
N
F
q
n
/
F
q
d
(
f
(
x
1
,...,x
n
))
−
1:1
≤
d<n,d
|
n
}
)
⊂ A
Note that there is a group operation on
T
n
(
F
q
), given by polynomials, inherited from
F
q
n
. Hence, ignoring the inverse map,
multiplication in
T
n
(
F
q
) satisfies our informal defi-
nition of an algebraic group.
Lemma 6.2.2
Let the notation be as above.
∈ F
q
n
:N
F
q
n
/
F
q
d
(
g
)
1. G
q,n
={
g
=
1
for all
1
≤
d<nsuch that d
|
n
}
.
2.
T
n
(
F
q
)
is isomorphic as a group to G
q,n
.
3.
#
T
n
(
F
q
)
=
n
(
q
)
.
Proof
For the first statement note that
n/d
−
1
g
q
di
g
(
q
n
−
1)
/
(
q
d
−
1)
.
N
F
q
n
/
F
q
d
(
g
)
=
=
i
=
0
2
The plural of “torus” is “tori”.