Cryptography Reference
In-Depth Information
2
3
One therefore defines a birational map
g
:
A
→ A
by
.
1
a
b
g
:(
a,b
)
→
b
2
,
b
2
,
1
−
a
2
+
ab
−
1
−
a
2
+
ab
−
1
−
a
2
+
ab
−
b
2
2
to
G
q,
6
is (
f
(
g
(
a,b
))
Finally, the map decomp
6
from
A
+
θ
)
/
((
f
(
g
(
a,b
))
+
θ
). It is then
straightforward to compute comp
6
.
Exercise 6.4.5
Let
q
be a prime power and
ζ
9
a primitive 9th root of unity in
F
q
. Show
that
F
q
(
ζ
9
)
= F
q
6
if and only if
q
≡
2
,
5(mod9).
2
induced from
G
q,
6
, but this is not an efficient way to compute. Instead, to compute comp
6
(
g
n
)from
comp
6
(
g
) one decompresses to obtain an element
g
A
In principle, one can write down the partial group operations on
∈
G
q,
6
(or
G
q
3
,
2
), computes
g
n
, and
then compresses again.
6.4.2 XTR
An excellent survey of work in this area is the thesis of Stam [
520
].
The Galois group of
F
q
2
is cyclic of order 3 and generated by the
q
2
-power Frobenius
map
σ
. One can consider the set
G
q,
6
/
F
q
6
/
σ
=
G
q,
6
/
Gal(
F
q
6
/
F
q
2
) of equivalence classes
σ
i
(
g
)for0
under the relation
g
2. This gives an algebraic group quotient, which
was named
XTR
8
by Lenstra and Verheul. The goal is to give a compressed representation
for this quotient; this is achieved by using the trace with respect to
≡
≤
i
≤
F
q
6
/
F
q
2
.
g
1
+
q
2
+
q
4
Lemma 6.4.6
Let g
∈
G
q,
6
. Let t
=
Tr
F
q
6
/
F
q
2
(
g
)
∈ F
q
2
. Then
N
F
q
6
/
F
q
2
(
g
)
=
=
1
x
3
tx
2
t
q
x
and the characteristic polynomial of g over
F
q
2
is χ
g
(
x
)
=
−
+
−
1
.
Proof
The first claim follows since
g
q
2
−
q
+
1
1 and (
q
2
1)(
q
2
q
4
=
−
q
+
+
q
+
1)
=
+
g
q
2
)(
x
g
q
4
)
q
2
x
3
tx
2
+
1. Now, write (
x
−
g
)(
x
−
−
=
−
+
sx
−
1. Since this polynomial
g
q
2
is fixed by Gal(
F
q
6
/
F
q
2
) it follows that
s,t
∈ F
q
2
. Indeed,
t
=
Tr
F
q
6
/
F
q
2
(
g
)
=
g
+
+
g
q
4
g
q
−
1
g
−
q
.Also
=
g
+
+
g
1
+
q
2
g
1
+
q
4
g
q
2
+
q
4
g
q
g
1
−
q
g
−
1
.
s
=
+
+
=
+
+
Finally,
s
q
g
q
2
g
q
2
−
q
g
−
q
t
q
.
=
+
+
=
t
, from which we have
s
=
This result shows that one can represent an equivalence class of
g
∈
G
q,
6
/
Gal(
F
q
6
/
F
q
2
)
using a single element
t
∈ F
q
2
, as desired. It remains to explain how to perform exponenti-
ation in the quotient (as usual, the quotient structure is not a group and so it makes no sense
to try to compute a general group operation on it).
x
3
tx
2
t
q
x
Exe
rc
ise 6.4.7
Write
f
(
x
)
=
−
+
−
1for
t
∈ F
q
2
. Prove that if
f
(
a
)
=
0for
∈ F
q
then
f
(
a
−
q
)
a
=
0. Hence, prove that either
f
(
x
) is irreducible over
F
q
2
or splits
completely over
F
q
2
.
8
XTR is an abbreviation for ECSTR, which stands for “Efficient and Compact Subgroup Trace Representation”.
