On the $k$-error linear complexity of binary sequences derived from polynomial quotients

Abstract

We investigate the $k$-error linear complexity of $p^2$-periodic binary sequences defined from the polynomial quotients (including the well-studied Fermat quotients), which is defined by $$q_{p,w}(u)\equiv \frac{u^w-u^{wp}}{p}\mathrm{mod}p\mathrm{with}0\le q_{p,w}(u)\le p-1,u\ge 0,$$ where $p$ is an odd prime and $1\le w<p$. Indeed, first for all integers $k$, we determine exact values of the $k$-error linear complexity over the finite field $\F_2$ for these binary sequences under the assumption of f2 being a primitive root modulo $p^2$, and then we determine their $k$-error linear complexity over the finite field $\F_p$ for either $0\le k<p$ when $w=1$ or $0\le k<p-1$ when $2\le w<p$. Theoretical results obtained indicate that such sequences possess `good' error linear complexity.

2 figures

References in corpus (3)

• Trace representation and linear complexity of binary sequences derived from Fermat quotients
• Fermat quotients: Exponential sums, value set and primitive roots
• The Arithmetic of Carmichael Quotients

Cited by in corpus (8)

• On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients
• Linear Complexity of A Family of Binary $p{q}^2$-periodic Sequences From Euler Quotients
• Linear complexity problems of level sequences of Euler quotients and their related binary sequences
• A further study on the linear complexity of new binary cyclotomic sequence of length $p^r$
• Trace representation of pseudorandom binary sequences derived from Euler quotients
• Linear complexity of Legendre-polynomial quotients
• Polynomial quotients: Interpolation, value sets and Waring's problem
• On error linear complexity of new generalized cyclotomic binary sequences of period $p^2$