BINARY SEQUENCES DERIVED FROM DIFFERENCES OF CONSECUTIVE QUADRATIC RESIDUES

摘要

For a prime p >= 5 let q(0), q(1), . . . , q((p-3)/2) be the quadratic residues modulo p in increasing order. We study two (p-3)/2-periodic binary sequences (d(n)) and (t(n)) defined by d(n) = q(n) + q(n+1) mod 2 and t(n) = 1 if q(n+1) = q(n) + 1 and t(n) = 0 otherwise, n = 0,1, ... , (p- 5)/2. For both sequences we find some sufficient conditions for attaining the maximal linear complexity (p - 3)/2. @@@ Studying the linear complexity of (d(n)) was motivated by heuristics of Caragiu et al. However, (d(n)) is not balanced and we show that a period of (d(n)) con-tains about 1/3 zeros and 2/3 ones if p is sufficiently large. In contrast, (t(n)) is not only essentially balanced but also all longer patterns of length s ap-pear essentially equally often in the vector sequence (t(n), t(n+1), ... , t(n+s-1)), n = 0, 1, ... , (p - 5)/2, for any fixed s and sufficiently large p.

关键词