Statement:
Suppose a given amount of bits of scrambler \(n \in \mathbb{N}\). Then there exist \(2^n \cdot \left( 2^n – 1 \right)\) scramblers of the length \(n\).
Proof:
Key of the scrambler – certain sequence of bits of the length \(n\). After reviewing key as vector of set \(\{ 0, 1 \} ^n\), it’s possible to make conclusion, that in total there exist \(2^n\) keys of the length \(n\). (That can also be proven with usage of simple combinatorial rule of production: on the first position of the key we can put two possible elements – \(0\) and \(1\), on second, \(\ldots\), n-th – same. According to the combinatorial rule of production, have: \(2 \cdot 2 \cdots 2 = 2^n\))
Shift registers of the scrambler set a selection of bits from the key, according to which the XOR-sum will be formed. According to the theorem “About amount of XOR-sums over the given sequence of bits”, there exist \(2^n-1\) of such selections.
Further, according to the combinatorial rule of production we have, that amount of every possible states of scrambler (which is defined by states of the key and shift registers) equals \(2^n \cdot \left( 2^n – 1 \right)\). Theorem is proven.