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)
Search WWH ::




Custom Search