Cryptography Reference
In-Depth Information
Proof
Clearly, eve
ry
element
g
=
(
a
+
θ
)
/
(
a
+
θ
) satisfies
gg
=
1. It is also easy to check
a
. Hence, we have obtained
q
dis-
tinct elements of
G
q,
2
. The missing element is evidently 1 and the result follows.
(
a
+
θ
)
/
(
a
+
that (
a
+
θ
)
/
(
a
+
θ
)
=
θ
) implies
a
=
Exercise 6.3.5
Determine the value for
a
such that (
a
+
θ
)
/
(
a
+
θ
)
=−
1.
Lemma 6.3.6
Let g
=
u
+
vθ
∈
G
q,
2
, g
=±
1
. Then u
+
vθ
=
(
a
+
θ
)
/
(
a
+
θ
)
for the
unique value a
=
(
u
+
1)
/v.
Proof
The value
a
must satisfy
a
+
θ
=
(
u
+
vθ
)(
a
+
θ
)
=
ua
+
uθ
+
avθ
+
vθθ
=
(
ua
−
Au
+
Bv
)
+
θ
(
av
−
u
)
.
Equating coefficients of
θ
gives
av
=
u
+
1 and the result follows as long as
v
=
0 (i.e.,
g
=±
1).
The above results motivate the following definition.
1
Definition 6.3.7
The
T
2
decom
pr
ession map
is the function decomp
2
:
A
→
G
q,
2
given
=
+
+
by decomp
2
(
a
)
(
a
θ
)
/
(
a
θ
).
T
2
compression map
is the function comp
2
:
G
q,
2
−{
−
}→A
1
The
1
,
1
given by
comp
2
(
u
+
vθ
)
=
(
u
+
1)
/v
.
Lemma 6.3.8
The maps
comp
2
and
decomp
2
are injective. The compression map is not
defined at
±
1
.Ifg
∈
G
q,
2
−{
1
,
−
1
}
then
decomp
2
(comp
2
(
g
))
=
g.
Exercise 6.3.9
Prove Lemma
6.3.8
.
1
,
Alert readers will notice that the maps comp
2
and decomp
2
are between
G
q,
2
and
A
1
. For completeness we now give a map from
G
q,
2
to
2
.
rather than between
T
2
and
A
T
2
⊂ A
T
2
and
A
1
, which prove that
T
2
is indeed
From this, one can deduce birational maps between
rational.
Lemma 6.3.10
An element of the form
(
a
+
θ
)
/
(
a
+
θ
)
∈
G
q,
2
corresponds to the element
a
2
−
B
2
a
−
A
B
,
a
2
−
aA
+
a
2
−
aA
+
B
of
T
2
.
Proof
Let (
x,y
) be the image point in
T
2
. In other words
(
a
+
θ
)
/
(
a
+
θ
)
=
x
+
yθ
and so
a
+
θ
=
(
x
+
yθ
)(
a
+
θ
)
=
(
ax
+
By
−
Ax
)
+
θ
(
ay
−
x
). Equating coefficients
gives the result.
Exercise 6.3.11
Prove that
T
2
is rational.