On the 4-adic complexity of the two-prime quaternary generator
This work addresses security concerns in cryptography by analyzing the complexity of quaternary sequences, but it is incremental as it extends prior results from binary to quaternary cases.
The paper tackles the problem of determining the 4-adic complexity for quaternary sequences generated by a two-prime method, showing that it exceeds a lower bound of pq - log_4(pq^2) - 1 when p < q, making it resistant to rational approximation attacks.
R. Hofer and A. Winterhof proved that the 2-adic complexity of the two-prime (binary) generator of period $pq$ with two odd primes $p\neq q$ is close to its period and it can attain the maximum in many cases. When the two-prime generator is applied to producing quaternary sequences, we need to determine the 4-adic complexity. We present the formulae of possible values of the 4-adic complexity, which is larger than $pq-\log_4(pq^2)-1$ if $p<q$. So it is good enough to resist the attack of the rational approximation algorithm.