Information Technology Reference
In-Depth Information
3M inR sut
Let
t
be the smallest positive integer for which
R
e
(
u
0
)=
R
f
(
u
0
) whenever
e
≡
f
(mod
t
). Note that
t
|
p
+1and
T
is the multiplicative order of
e
modulo
t
.
Theorem 1.
For every fixed integer
ν
≥
1
and nontrivial multiplicative char-
acter
χ
of
IF
p
we have
S
χ
=
O
T
1
−
4
ν
(
ν
+1)
,
2
ν
+1
2
ν
(
ν
+1)
t
1
2(
ν
+1)
p
ν
+2
where the implied constant depends only on
ν
.
Proof.
We put
h
=
t
2(
ν
+1)
.
1
ν
ν
+1
T
−ν
ν
+1
p
p
1
/
2(
ν
+1)
,
thus Lemma 1
Because
t
≥
T
, for this choice of
h
we obtain
h
≥
applies.
Because the sequence (
u
n
) is purely periodic, for any
k
∈
ZZ
t
,wehave:
T−
1
S
χ
=
χ
(
R
e
n
+
k
(
u
0
))
.
(4)
n
=0
Let
K
be the subgroup of
U
t
generated by
e
.Thus#
K
=
T
. We select
r
as in Lemma 1 and let
L
be the subset of
K
which satisfies the corresponding
congruence. We denote
L
=#
L
.Inparticular,
L
hT/t
.
By (4) we have
T−
1
LS
χ
=
χ
(
R
e
n
+
k
(
u
0
))
.
n
=0
k∈L
Applying the Holder inequality, we derive
χ
(
R
e
n
+
k
(
u
0
))
2
ν
T
2
ν−
1
T−
1
L
2
ν
2
ν
|
S
χ
|
≤
.
(5)
n
=0
k∈L
r
≤
1, be defined by the congruence
rr
≡
Let 1
≤
t
−
1(mod
t
). By (3) we
obtain
R
e
n
+
k
(
u
0
)
≡
R
e
n
+
k
rr
(
u
0
)
≡
R
re
k
(
R
r
e
n
(
u
0
))
(mod
p
)
.
Obviously, the values of
r
e
n
,
n
=0
,...,T
1, are pairwise distinct modulo
t
.
Thus, from the definition of
t
, we see that the values of
R
r
e
n
(
u
0
)arepairwise
distinct. Therefore, from (5) we derive
−
χ
(
R
re
k
(
u
))
2
ν
L
2
ν
2
ν
T
2
ν−
1
|
S
χ
|
≤
.
u∈
IF
p
k∈L