Computing the k-error 2-adic complexity of a binary sequence of period pn

摘要

Cryptographically strong sequences should have a large 2-adic complexity to thwart the known feedback with carry shift register (FCSR) synthesis algorithms. At the same time the change of a few terms should not cause a significant decrease of the 2-adic complexity. This requirement leads to the concept of the k-error 2-adic complexity. In this paper, an algorithm for computing the k-error 2-adic complexity of the binary sequence with period N=pn, p is a prime, is proposed by using the 2-adic complexity synthesis algorithm of Wilfried Meidl, and the Stamp-Martin algorithm. This algorithm is the first concrete construction of the algorithm for calculating the k-error 2-adic complexity. Using the algorithm proposed, the upper bound of the k-error 2-adic complexity can be obtained in n steps.