On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients
This work addresses a theoretical problem in cryptography and pseudorandom sequence analysis, offering incremental advancements in understanding the security properties of specific sequences.
The paper tackles the problem of analyzing the k-error linear complexity of pseudorandom binary sequences derived from Euler quotients modulo powers of odd primes, establishing a recursive relation for r≥3 and providing exact values for r=3, showing that the complexity does not decrease dramatically for k < p^(r-2)(p-1)^2/2.
We investigate the $k$-error linear complexity of pseudorandom binary sequences of period $p^{\mathfrak{r}}$ derived from the Euler quotients modulo $p^{\mathfrak{r}-1}$, a power of an odd prime $p$ for $\mathfrak{r}\geq 2$. When $\mathfrak{r}=2$, this is just the case of polynomial quotients (including Fermat quotients) modulo $p$, which has been studied in an earlier work of Chen, Niu and Wu. In this work, we establish a recursive relation on the $k$-error linear complexity of the sequences for the case of $\mathfrak{r}\geq 3$. We also state the exact values of the $k$-error linear complexity for the case of $\mathfrak{r}=3$. From the results, we can find that the $k$-error linear complexity of the sequences (of period $p^{\mathfrak{r}}$) does not decrease dramatically for $k<p^{\mathfrak{r}-2}(p-1)^2/2$.