Cryptography Reference
In-Depth Information
6
Tori, LUC and XTR
Recall from Example
5.1.4
that
F
q
satisfies our informal notion of an algebraic group.
This chapter concerns certain subgroups of the multiplicative group of finite fields of the
form
F
q
n
with
n>
1. The main goal is to find short representations for elements. Alge-
braic tori give short representations of elements of certain subgroups of
F
q
n
. Traces can be
used to give short representations of certain algebraic group quotients in
F
q
n
, and the most
successful implementations of this are called LUC and XTR. These ideas are sometimes
called
torus-based cryptography
or
trace-based-cryptography
, though this is mislead-
ing: the issue is only about representation of elements and is independent of any specific
cryptosystem.
6.1 Cyclotomic subgroups of finite fields
. A complex number
z
is an
n
th
root of unity
if
z
n
Definition 6.1.1
Let
n
∈ N
=
1, and is
a
primitive
n
th root of unity if
z
n
1 and
z
d
=
=
1 for any divisor
d
|
n
with 1
≤
d<n
.
The
n
th
cyclotomic polynomial
n
(
x
) is the product (
x
−
z
) over all primitive
n
th roots
of unity
z
.
Lemma 6.1.2
Let n
∈ N
. Then:
1.
deg(
n
(
x
))
=
ϕ
(
n
)
.
∈ Z
2.
n
(
x
)
[
x
]
.
3.
x
n
−
1
=
d
(
x
)
.
d
|
n,
1
≤
d
≤
n
4. If m
∈ N
is such that m
=
n then
gcd(
n
(
x
)
,
m
(
x
))
=
1
.
5.
(
x
n/d
1)
µ
(
d
)
n
(
x
)
=
−
d
|
n
where µ
(
d
)
is the Mobius function (Definition 4.3 of [
420
]).
