Information Technology Reference
In-Depth Information
The following facts can be found in [9]. The Redei function
R
e
(
X
)isapermu-
tation of IF
p
if and only if gcd(
e, p
+ 1) = 1, the set of these permutations is a
group with respect to the composition which is isomorphic to the group of units
of
ZZ
p
+1
. In particular for indices
m, n
with gcd(
m, p
+1)=gcd(
n, p
+1)= 1 we
have
R
m
(
R
n
(
u
)) =
R
mn
(
u
)=
R
n
(
R
m
(
u
))
for all
u
∈
IF
p
.
(3)
For further background on Redei functions we refer to [5,9,10].
We consider generators (
u
n
) defined by
u
n
+1
=
R
e
(
u
n
)
,
n
≥
0
,
gcd(
e, p
+1)=1
,
with a Redei permutation
R
e
(
X
) and some initial element
u
0
∈
IF
p
.These-
quences (
u
n
) are purely periodic and the period length
T
divides
ϕ
(
p
+1),
where
ϕ
denotes Euler's totient function. For details we refer to [9, Lemma 3.5].
Although we follow the same general method of bounding character sums as
in [2], the details of the crucial step that a certain auxiliary polynomial, see (6)
below, is not, up to a multiplicative constant, an
s
th power of a polynomial,
where
s
denotes the order of
χ
,ismoreintricate.
2 Preliminaries
For an integer
t>
1wedenoteby
ZZ
t
the residue ring modulo
t
and always
assume that it is represented by the set
{
0
,
1
,...,t
−
1
}
.Asusual,wedenoteby
U
t
the set of invertible elements of
ZZ
t
.
We recall Lemma 2 from [1].
Lemma 1.
For any set
K⊆U
t
of cardinality
#
K
=
K
, any fixed
1
≥
δ>
0
t
δ
and any integer
h
≥
there exists an integer
r
∈U
t
such that the congruence
rk
≡
y
(mod
t
)
,
k
∈K
,
0
≤
y
≤
h
−
1
,
has
Kh
t
L
r
(
h
)
solutions
(
k, y
)
.
We also need the
Weil bound
for character sums which we present in the following
form, see e.g. [6, Theorem 5.41].
Lemma 2.
Let
χ
be a multiplicative character of
IF
p
of order
s>
1
and let
F
(
X
)
IF
p
[
X
]
be a polynomial of positive degree that is not, up to a multiplica-
tive constant, an
s
th power of a polynomial. Let
d
be the number of distinct roots
of
F
(
X
)
in its splitting field over
IF
p
. Then we have
∈
1)
p
1
/
2
.
χ
(
F
(
x
))
≤
(
d
−
x∈
IF
p
