Computer Security and Cryptography

8.7 COMBINING MULTIPLE LINEAR FEEDBACK SHIFT REGISTERS

Figure 8.7 shows how linear feedback shift registers can be combined by XORing their outputs. The XOR of periodic sequence with periods {P_i} is periodic with period equal to the least common multiple P = 1cm{P_i} of the individual periods. (Note, the least common multiple of integers {n_i} is the smallest integer n divisible by each of the {n_i}.)

When the characteristic polynomials are primitive, and their exponents 2^N_i − 1 (0 ≤ i < k) which are relatively prime in pairs

the period of the combined generator is (Note, the greatest common divisor gcd{n₁, n₂} is the largest integer n that divides both the n₁ and n₂; if 1 = gcd{n₁, n₂}, the integers are relatively prime.) Just as Vernam additively combined tapes of relatively prime lengths to produce a tape with a much longer period, the same result is achieved by additively combining LFSRs of suitable total lengths to produce a LFSR with a much larger period.

Figure 8.7 The XOR of k linear feedback shift registers.