Cryptography Reference
In-Depth Information
Pic
0
T
2
g
a
1
T
2
g
−
1
a
1
q
g
−
1
T
F
q
(
C
) then
P
(
π
)
D
≡
0. In other words, if
P
(
T
)
=
+
+···+
+
q
g
then
π
2
g
(
D
)
[
a
1
]
π
2
g
−
1
(
D
)
[
a
1
q
g
−
1
]
π
(
D
)
[
q
g
]
D
+
+···+
+
≡
0
(10.19)
where the notation [
n
]
D
is from Definition
10.5.1
.
Exercise 10.7.11
Let
C
be a curve over
F
q
with Mumford representation (
u
(
x
)
,v
(
x
)). Let
π
be the
q
-power Frobenius map on
C
.
For a polynomial
u
(
x
)
F
q
and
D
a reduced divisor on
C
over
=
i
=
0
u
i
x
i
define
u
(
q
)
(
x
)
=
i
=
0
u
i
x
i
. Show that the Mumford
representation of
π
∗
(
D
)is(
u
(
q
)
(
x
)
,v
(
q
)
(
x
)).
Example 10.7.12
(Koblitz [298]) Let
a
∈{
0
,
1
}
and consider the genus 2 curve
C
a
:
y
2
x
5
ax
2
+
xy
=
+
+
1 over
F
2
. One can verify that #
C
0
(
F
2
)
=
4, #
C
1
(
F
2
)
=
2 and
#
C
0
(
F
2
2
)
=
#
C
1
(
F
2
2
)
=
4. Hence, the characteristic polynomial of Frobenius is
P
(
T
)
=
4. One can determine #Pic
0
T
4
+
−
1)
a
T
3
+
−
1)
a
T
+
∈ N
(
2(
F
2
n
(
C
a
) for any
n
.If
n
is com-
n
one has #Pic
0
#Pic
0
|
|
posite and
m
F
2
m
(
C
a
)
F
2
n
(
C
a
). For cryptographic applications one
would like #Pic
0
F
2
n
(
C
a
)
/
#Pic
0
F
2
(
C
a
) to be prime, so restrict attention to primes values for
n
.
For example, taking
n
=
113 and
a
=
1 gives group order 2
·
r
where
r
=
539
···
381 is a
225-bit prime.
If
D
Pic
0
F
2
n
(
C
1
) then
π
4
(
D
)
π
3
(
D
)
∈
−
−
[2]
π
(
D
)
+
[4]
D
≡
0 where
π
is the map
induced on Pic
0
(
x
2
,y
2
)on
C
.
F
2
n
(
C
1
) from the 2-power Frobenius map
π
(
x,y
)
=
A major result, whose proof is beyond the scope of this topic, is Tate's isogeny theorem.
Theorem 10.7.13
(Tate) Let A and B be Abelian varieties over a field
F
q
. Then A is
F
q
-
isogenous to B if and only if P
A
(
T
)
=
P
B
(
T
)
. Similarly, A is
F
q
-isogenous to an Abelian
subvariety of B if and only if P
A
(
T
)
|
P
B
(
T
)
.
Proof
See [
540
].
Exercise
10.7.14
gives a direct proof of Theorems
10.7.1
and
10.7.5
for genus 2 curves
with ramified model.
Exercise 10.7.14
Let
q
be an odd prime power. Let
F
(
x
)
∈ F
q
[
x
] be square-free
and of degree 5. Then
C
:
y
2
=
F
(
x
) is a hyperelliptic curve over
F
q
of genus 2 with
q
n
a ramified model. For
n
=
1
,
2let
N
n
=
#
C
(
F
q
n
) and define
t
n
=
+
1
−
N
n
so that
q
n
(
t
1
−
N
n
=
+
1
−
t
n
. Define
a
1
=−
t
1
and
a
2
=
t
2
)
/
2. Show, using direct calculation
and Exercise
10.4.4
, that Pic
0
F
q
(
C
) has order
q
2
+
a
1
(
q
+
1)
+
a
2
+
1.
10.8 Supersingular curves
Recall from Theorem
10.6.1
that if
C
is a curve of genus
g
over a field
k
of characteristic
p
then #Pic
0
k
p
g
.
(
C
)[
p
]
≤