On the discrepancy and linear complexity of some counter-dependent recurrence sequences

We prove a discrepancy bound “on average” over all initial values aα(0)=α of congruential pseudorandom numbers obtained from the sequences aα(n) over a finite field of prime order defined by aα(n)=naα(n–1)+1, n=1,2,..., using new bounds on certain exponential sums. Moreover, we prove a lower bound on the linear complexity of this sequence showing that its structural properties are close to be best possible.9 page(s