Binary sequences derived from differences of consecutive quadratic residues

Abstract: For a prime

p g e 5

let

q_{0}, q_{1}, l d o t s, 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

and

t_{n} = 1

if

q_{n + 1} = q_{n} + 1

and

t_{n} = 0

otherwise,

n = 0, 1, l d o t s, (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})

contains 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

appear essentially equally often in the vector sequence

(t_{n}, t_{n + 1}, l d o t s, t_{n + s - 1})

,

n = 0, 1, l d o t s, (p - 5) / 2

, for any fixed

s

and sufficiently large

p

.

Cites Work

Cited In (1)

Recommendations

This page was built for publication: Binary sequences derived from differences of consecutive quadratic residues