Cryptography Reference
In-Depth Information
LEMMA 4.26
Let
p
≡
1(mod4)
be prime.Then
χ
4
(
b
)
=
p −
1
if
≡
0(mod )
0
if
≡
0(mod
.
∈
F
p
b
PROOF
If
≡
0 (mod 4), all the terms in the sum are 1, so the sum is
≡
0 (mod 4), then
χ
4
(
g
)
p −
1. If
= 1. Multiplying by
g
permutes the
elements of
F
p
,so
χ
4
(
g
)
b
χ
4
(
b
)
=
b
χ
4
(
gb
)
=
c
χ
4
(
c
)
,
∈
F
p
∈
F
p
∈
F
p
which is the original sum. Since
χ
4
(
g
)
= 1, the sum must be 0.
Define the
Jacobi sums
by
J
(
χ
2
,χ
4
)=
a∈
F
p
a
χ
2
(
a
)
j
χ
4
(1
a
)
.
−
=1
PROPOSITION 4.27
J
(
χ
2
,χ
4
)=
2
=
p
.
−
1
and
|
J
(
χ
2
,χ
4
)
|
PROOF
The first equality is proved as follows.
J
(
χ
2
,χ
4
)=
a∈
F
p
a
χ
2
(
a
)
χ
4
(1
− a
)
2
=
a
χ
2
(
a
)
χ
2
(1
− a
)
,
=0
,
1
=1
since
χ
4
=
χ
2
.Since
χ
2
(
a
)=
±
1, we have
χ
2
(
a
)=
χ
2
(
a
)
−
1
so the sum equals
χ
2
1
−
a
.
a
)=
a
χ
2
(
a
)
−
1
χ
2
(1
−
a
a
=0
,
1
=0
,
1
1
x
The map
x
→
1
−
gives a permutation of the set of
x
∈
F
p
,
x
=0
,
1.
Therefore, letting
c
=1
−
1
/a
, we obtain
χ
2
1
a
−
1
=
c
χ
2
(
−c
)=
−χ
2
(
−
1)
,
a
=0
,
1
=0
,
1
by Lemma 4.26. Since
g
(
p−
1)
/
2
≡−
1(mod
p
) (both have order 2 in the cyclic
group
F
p
), we have
1=(
±
1)
2
=
χ
2
(
g
(
p−
1)
/
4
)
2
=
χ
2
(
g
(
p−
1)
/
2
)=
χ
2
(
−
1)
.
Search WWH ::
Custom Search