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”.
Search WWH ::




Custom Search