An algorithm for the spectral immunity of binary sequence with period 2n

To resist the fast algebraic attack and fast selective discrete Fourier transform attacks, spectral immunity of a sequence or a Boolean function was proposed. At the same time, an algorithm to compute the spectral immunity of the binary sequence with odd period N was presented, here N is a factor of 2 ⁿ ? 1, where n is an integer. The case is more complicated when the period is even. In this paper, we compute linear complexity of every orthogonal sequence of a given sequence using Chan-Games algorithm and k - error linear complexity algorithm. Then, an algorithm for spectral immunity of binary sequence with period N = 2 ⁿ is obtained. Furthermore, the time complexity of this algorithm is proved to be O(n).