Linear complexity of generalized cyclotomic binary sequences of order 2 (Q1266420): Difference between revisions

Cyclotomic sequences have quite good randomness properties and are potentially interesting for data encryption purposes. In this paper, given two odd primes \(p\) and \(q\), the author studies an associated sequence that is a generalized cyclotomic sequence of order 2. In case \(\text{gcd}(p-1, q-1)= 2\), he determines the linear complexity of this sequence. Let \(s^\infty= s_0s_1\cdots s_{n-1}\cdots\) be a periodic infinite sequence over a field \(F\). The linear complexity of \(s^\infty\) is defined to be the least positive integer \(\ell\) such that there are constants \(c_1,\dots, c_\ell\in F\) satisfying \(s_i= c_1s_{i-1}+ c_2s_{i-2}+\cdots+ c_\ell s_{i-\ell}\) for all \(i\geq \ell\). Thus, the linear complexity of a sequence is a measure of its randomness.