Cryptography Reference
In-Depth Information
a simpler equation, such as
θ
2
B
or
θ
2
=
+
θ
=
B
where
B
is “small”. Every element of
F
q
2
is of the form
u
+
vθ
w
h
ere
u,v
∈ F
q
.
θ
q
The
conjugate
of
θ
is
θ
=
=−
A
−
θ
.We
h
ave
θ
+
θ
=−
A
and
θθ
=
B
.The
conjugate of an element
g
=
u
+
vθ
∈ F
q
2
is
u
+
vθ
and
g
has
norm
u
2
Bv
2
.
N
F
q
2
/
F
q
(
g
)
=
(
u
+
vθ
)(
u
+
vθ
)
=
−
Auv
+
(6.2)
∈ F
q
2
such that
g
q
+
1
The group
G
q,
2
is defined to be the set of elements
g
=
1. Equiv-
vθ
such that
u
2
Bv
2
alently, this is the set of
u
+
−
Auv
+
=
1.
G
q,
2
then
g
−
1
g
q
Exercise 6.3.1
Show that if
g
=
u
+
vθ
∈
=
=
u
+
vθ
=
(
u
−
Av
)
+
(
−
v
)
θ
. Hence, inversion in
G
q,
2
is cheaper than a general group operation (especially if
A
=
0or
A
is “small”).
= F
q
(
θ
) where
θ
2
Exercise 6.3.2
Suppose
q
is not a power of 2. Suppose
F
q
2
+
Aθ
+
B
=
0 and multiplying an element of
F
q
by
A
or
B
has negligible cost (e.g.,
A
=
0 and
B
=
1).
F
q
2
using 3
multiplications (respectively: 3 squarings; one inversion, 3 multiplications and 2 squarings)
in
Show that one can compute a product (respectively: squaring; inversion) in
F
q
. Ignore the cost of additions and multiplication by small constants such as 2 (since
they are significantly faster to perform than multiplications etc).
≡
F
q
2
as
Exercise 6.3.3
Suppose
q
3 (mod 4) is prime. Show that one can represent
F
q
(
θ
) where
θ
2
+
=
0. Show that, using this representation, one can compute a product
(respectively: squaring; inversion; square root) in
1
F
q
2
using 3 multiplications (respectively:
2 multiplications; one inversion, 2 squarings and 2 multiplications; 2 square roots, one
inversion, one Legendre symbol, one multiplication and 2 squarings) in
F
q
. Ignore the cost
of additions.
6.3.1 The torus
T
2
Recall that
G
q,
2
can be represented as the
F
q
-points of the algebraic torus
T
2
=
2
, where
f
:
2
(
V
(N
F
q
2
/
F
q
(
f
(
x,y
))
−
1)
⊂ A
A
F
q
)
→ F
q
2
. By equation (
6.2
), an affine equa-
T
2
is
V
(
x
2
By
2
tion for
1). Being a conic with a rational point, it is immediate
from general results in geometry (see Exercise
5.5.14
for a special case) that
−
Axy
+
−
T
2
is birational
1
.
The next two results give a more algebraic way to show that
A
with
T
2
is rational. Rather than
directly constructing a birational map from
T
2
to
A
1
,wegovia
G
q,
2
. Lemma
6.3.4
provides
1
(
1
(
a map from
A
F
q
)to
G
q,
2
, while Lemma
6.3.6
provides a map from
G
q,
2
to
A
F
q
).
Lemma 6.3.4
The set G
q,
2
⊆ F
q
2
is equal to the set
{
(
a
+
θ
)
/
(
a
+
θ
):
a
∈ F
q
}∪{
1
}
.
