Information Technology Reference
In-Depth Information
On the Average Distribution of Power Residues
and Primitive Elements in Inversive and
Nonlinear Recurring Sequences
Ayca ¸esmelioglu
1
and Arne Winterhof
2
1
Sabancı University, Orhanlı, Tuzla, 34956 Istanbul, Turkey
cesmelioglu@su.sabanciuniv.edu
2
Johann Radon Institute for Computational and Applied Mathematics (RICAM)
Austrian Academy of Sciences, Altenbergerstr. 69, 4040 Linz, Austria
arne.winterhof@oeaw.ac.at
Abstract.
We estimate character sums with inversive and nonlinear
recurring sequences 'on average' over all initial values and obtain much
stronger bounds than known for 'individual' sequences. As a consequence,
we present results 'on average' about the distribution of power residues
and primitive elements in such sequences.
On the one hand our bounds can be regarded as results on the pseu-
dorandomness of inversive and nonlinear recurring sequences. On the
other hand they shall provide a further step to ecient deterministic al-
gorithms for finding non-powers and primitive elements in a finite field.
1
Introduction
Let
q
be a prime power and
F
q
the finite field of
q
elements. For
q
≥
4andgiven
∈
F
q
,
b
F
q
defined by
ψ
(
w
)=
aw
q−
2
+
b
,
a
∈
F
q
,let
ψ
be the permutation of
w
∈
F
q
.Let(
u
n
)=
u
0
,u
1
,...
be the sequence of elements of
F
q
obtained by the
recurrence relation
u
n
+1
=
ψ
(
u
n
)
,
n
≥
0
,
∈
F
q
. Because of the property
w
q−
2
=
w
−
1
with some initial value
u
0
=
ϑ
for
w
= 0 the sequence (
u
n
) is called
inversive recurring sequence
.Itisobviousthat
the sequence (
u
n
) is purely periodic with least period
t
ϑ
≤
q
.
The inversive recurring sequence (
u
n
) belongs to the class of
nonlinear recur-
ring sequences
(
x
n
)=
x
0
,x
1
,...
obtained by
x
n
+1
=
f
(
x
n
)
,
n
≥
0
,
with some initial value
x
0
=
ϑ
∈
F
q
[
X
]ofdegree
at least two. Note that, if
f
(
X
) is a permutation polynomial, the sequence (
x
n
)
is purely periodic. We restrict ourselves to this case and denote the least period
again by
t
ϑ
≤
∈
F
q
and a polynomial
f
(
X
)
q
.
We study character sums over the sequences (
u
n
)and(
x
n
) 'on average' over
all initial values
ϑ
.