On the 2-Adic Complexity of the Two-Prime Generator
Richard Hofer, Arne Winterhof · IEEE Transactions on Information Theory · 2018
Hu introduced a simple method to compute the 2-adic complexity of any periodic binary sequence with ideal two-level autocorrelation. We extend this approach to some other sequences. First, we provide a substantially shorter proof of the maximality of the 2-adic complexity of the Legendre sequence of period N ≡ 1 mod 4 first proved by Xiong et al. Then, we show that the 2-adic complexity of the two-prime generator of period pq with two odd primes p≠q attains the maximum if (q + 1)/4 ≤ p ≤ 4q - 1. This result was only known for twin primes q = p+2 before. For arbitrary odd primes p ≠ q, we can still prove that the 2-adic complexity of the two-prime generator is close to its period.