**On the binary sequences with high $GF(2)$ linear complexities and low $GF(p)$ linear complexities**

*Hao Chen and Liqing Xu*

**Abstract: **Klapper [1] showed that there are binary sequences of period $q^n-1$
($q$ is a prime power $p^m$, $p$ is an odd prime)
with the maximal possible linear complexity $q^n-1$ when considered as sequences over $GF(2)$, while the sequences
have very low linear complexities when considered as sequences over $GF(p)$. This suggests that the binary sequences
with high $GF(2)$ linear complexities and low $GF(p)$ linear complexities are note secure in cryptography. In this note we
give some simple constructions of the binary sequences with high
$GF(2)$ linear complexities and low $GF(p)$ linear complexities. We
also prove some lower bounds on the $GF(p)$ linear complexities of
binary sequences and a lower bound on the number of the binary
sequences with high $GF(2)$ linear complexities and low $GF(p)$
linear
complexities .

**Category / Keywords: **secret-key cryptography / Cryptography, stream cipher, $GF(2)$ linear complexity, $GF(p)$ linear complexity

**Date: **received 22 Jul 2005

**Contact author: **chenhao at fudan edu cn

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Version: **20050730:162516 (All versions of this report)

**Short URL: **ia.cr/2005/241

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]