On the Average Distribution of Power Residues and Primitive Elements in Inversive and Nonlinear Recurring Sequences - Sequences and Their Applications-SETA 2008 - page 62

Note that the expected value of N− 1

n =0 χ ( y n ) for a 'truly' random sequence ( y n )

F q is θ ( N 1 / 2 ), see Section 5,
and (4) and (5) can be regarded as results on the pseudorandomness of the
sequences ( u n )and( x n ).
Using a standard technique, from (4) and (5) we derive results 'on average' on
the distribution of powers and primitive elements in the sequences ( u n )and( x n ).
These results shall provide a further step to ecient deterministic algorithms for
finding non-powers and primitive elements in a finite field where the construction
of short sequences containing non-powers and primitive elements is crucial.

over F q and a nontrivial multiplicative character of

2 Bounds on Character Sums of Inversive Sequences

In this section we estimate the sums
S χ,a,b ( N )=

2 ,

ϑ∈ F q |

S χ,a,b ( N, ϑ ) | 1 ≤ N ≤ T a,b .

Theorem 1. Let χ be a nontrivial multiplicative character of F q , then for 1 ≤

N ≤ T a,b we have

S χ,a,b ( N )= O max N 2 q 1 / 2 ,Nq .

Proof. We have

N− 1

χ ( ψ n ( ϑ )) χ ( ψ k ( ϑ ))

S χ,a,b ( N )=

n,k =0 ϑ∈ F q

N− 1

χ ( ψ n ( ϑ )) χ ( ψ k ( ϑ )) ≤ .

n,k =0 ϑ ∈ F q

For n = k ,thesumover ϑ is equal to q − 1 and thus

N− 1

χ ( ψ n ( ϑ )) χ ( ψ k ( ϑ ))

S χ,a,b ( N ) ≤ N ( q − 1) + 2 .

n,k =0
n>k

ϑ∈ F q

Since ψ is a permutation, we can write the previous sum as

N − 1

χ ( ψ n−k ( ϑ )) χ ( ϑ )

S χ,a,b ( N ) ≤ N ( q − 1) + 2

n,k =0
n>k

ϑ∈ F q

N− 1

χ ( ψ n−k ( ϑ ) ϑ q− 2 )

= N ( q − 1) + 2 .

n,k =0
n>k

ϑ∈ F q