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 ϑ .
 
Search WWH ::




Custom Search