ON LINEAR COMPLEXITY OF GENERALIZED SHRINKING-MULTIPLEXING GENERATOR
ZHANETA N. TASHEVA *
Faculty of Artillery, AAD and CIS, National Military University “V. Levski”, Faculty of Technical Sciences, University of Shumen, Shumen, Bulgaria.
*Author to whom correspondence should be addressed.
Abstract
The linear complexity of the Generalized Shrinking-Multiplexing Generator (GSMG), based on Linear Shift Feedback Registers (LFSRs), is investigated in this paper. The lower and upper bounds of linear complexity of its output binary Pseudo Random Sequences are established. It is proved that the linear complexity increases exponentially with the length of the control p-ary LFSR and the prime p used. Some linear complexity analysis is given. It is shown that the linear complexity of the GSMG based on LFSRs is greater than the linear complexity of the Shrinking Generator.
Keywords: Stream Cipher, clock controlled generators, shrinking generator, LFSR, linear complexity