How to produce a binary output sequence using LFSRs but with increased linear complexity? How to produce a binary output sequence using LFSRs but with increased linear complexity?


I have tried searching but i got confused on equation details. So can anyone help me with rather simple explanation on how to increase linear complexity i.e. with some diagram or so.
Thanks
One standard way is as follows. Given $n$ primitive LFSRs with lengths $L_i,i=1,\ldots,n$ such that $\gcd(L_i,L_j)=1,$ and a nonlinear boolean function $$f:\mathbb{F}_2^n \rightarrow \mathbb{F}_2$$ with $f(x_1,\ldots,x_n)$
you have output linear complexity
$$
f(L_1,\ldots,L_n)
$$
evaluated over the integers, where output of LFSR $L_i$ is input as the variable $x_i$ of the boolean function. This is called the combination generator.

So if, for example,
$$f(x_1,x_2,x_3)=x_1x_2+x_2x_3
$$
with
$L_1=31,L_2=32,L_3=33,$ the linear comlexity becomes $31\times 32+32\times 33=2048 $.

See the book Encyclopedia of Cryptography and Security on page 233 for a good discussion.