Linear Complexity of New Binary Sequence Derived From Polynomial Quotients Modulo p in General Case and Their Generalizations

Abstract

Pseudorandom sequences with large linear complexity have been widely applied in electronic countermeasures, mobile communication and cryptography. Linear complexity is considered as a primary security criterion to measure the unpredictability of pseudorandom sequences. This paper presents the linear complexity and minimal polynomial of a new family of binary sequences derived from polynomial quotients modulo an odd prime $p$ in general case. The results indicate that the sequences have high linear complexity, which means they can resist the linear attack against pseudo-noise or stream ciphers. Moreover, we generalize the result to the polynomial quotients modulo a power of $p$ in general case. Finally, we design a Gpqs stream cipher generator based on the generalized binary pseudorandom sequences to implement the sequences in hardware.

Keywords

• Pseudorandom sequences
• electronic countermeasures
• stream cipher
• linear complexity
• polynomial quotients