On the average distribution of power residues and primitive elements in inversive and nonlinear recurring sequences

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 pseudorandomness of inversive and nonlinear recurring sequences. On the other hand they shall provide a further step to efficient deterministic algorithms for finding non-powers and primitive elements in a finite field.