Trace representation and linear complexity of binary sequences derived from Fermat quotients
This work addresses theoretical problems in cryptography and coding theory, specifically for researchers studying pseudorandom sequences, but it is incremental as it builds on existing methods and results.
The paper tackles the problem of analyzing binary sequences derived from Fermat quotients modulo an odd prime, by describing their trace representations and determining linear complexity results. It confirms an earlier linear complexity result for binary threshold sequences and provides a new result for Legendre-Fermat quotient sequences under a specific condition.
We describe the trace representations of two families of binary sequences derived from Fermat quotients modulo an odd prime $p$ (one is the binary threshold sequences, the other is the Legendre-Fermat quotient sequences) via determining the defining pairs of all binary characteristic sequences of cosets, which coincide with the sets of pre-images modulo $p^2$ of each fixed value of Fermat quotients. From the defining pairs, we can obtain an earlier result of linear complexity for the binary threshold sequences and a new result of linear complexity for the Legendre-Fermat quotient sequences under the assumption of $2^{p-1}\not\equiv 1 \bmod {p^2}$.