Information Technology Reference
In-Depth Information
Besides the class of inversive recurring sequences there are two other classes of
nonlinear recurring sequences for which we know much better worst case bounds
than for a general nonlinear recurring sequence where
f
(
X
)iseitheraDickson
polynomial, see [2], or a Redei function, see [3].
Since for a nontrivial multiplicative character of
F
q
χ
(
y
n
)
2
N−
1
=
Nq
N−
1
(
q
−
1)
,
q
n
=0
(
y
0
,...,y
N
−
1
)
∈
F
the expected value of
N−
1
n
=0
χ
(
y
n
)
of a 'truly' random sequence (
y
n
)is
1
1
/
2
1
q
N
1
/
2
.
−
Besides the rather small character sum bounds inversive recurring sequences
have several other nice pseudorandomness properties as low linear complexity
[4] and small discrepancy [8,9]. Similar but weaker results are also known for
general nonlinear recurring sequences [4,7].
Finding an
s
th non-power is the crucial step in the design of deterministic
algorithms for solving equations over finite fields, see e.g. [1, Chapter 7]. Al-
gorithms for finding primitive elements in a finite field normally consist of two
parts: 1. Finding a short sequence containing at least one primitive element;
2. Testing primitiveness of the sequence elements, see e.g. [13, Chapter 2]. Our
results show that inversive recurring sequences are suitable for both algorithmic
problems for almost all initial values. However, it is still a problem to detect bad
initial values.
Acknowledgment
This paper was written during a pleasant stay of A. ¸ . to Linz. She wishes to
thank the Radon Institute for its hospitality. A. ¸ . was supported by Yousef
Jameel scholarship and in part by Tubitak and A.W. was supported in part by
the Austrian Science Fund (FWF) Grant P19004-N18.
References
1. Bach, E., Shallit, J.: Algorithmic number theory. Ecient algorithms. Foundations
of Computing Series, vol. 1. MIT Press, Cambridge (1996)
2. Gomez, D., Winterhof, A.: Character sums for sequences of iterations of Dick-
son polynomials. In: Mullen, G., et al. (eds.) Finite Fields and Applications Fq8,
Contemporary Mathematics (to appear)
3. Gomez, D., Winterhof, A.: Multiplicative Character Sums of Recurring Sequences
with Redei Functions. In: Proceedings SETA 2008 (to appear, 2008)