**Question: Instead of modulo 2, Alice have a LFSR works with modulo 3. The formula of this LFSR is** X_{n+3} = X_n + 2X_{n+1}+2X_{n+2} **(mod 3), where the initial values are X0=0, X1=1, X2=2.(a) Compute first 20 outputs (including X0, X1 and X2) of the above LFSR.(b) What is the period? What is the largest period of a LFSR with 3 registers under modulo 3?**

**Solution: ** (a) the output for (a) 01202011121100120201.

(b) Clearly from part a) output is

0 | 1 | 2 | 0 | 2 | 0 | 1 | 1 | 1 | 2 | 1 | 1 | 0 | 0 | 1 | 2 | 0 | 2 | 0 | 1 |

X0 | X1 | X2 | x3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | X11 | X12 | X13 | X14 | X15 | X16 | X17 | X18 | X19 |

So, clearly after X12 value starts repeating

X13=X0, X14=X1,X15=X2

So, period = 13 (number of steps from X0 to X12)

Maximum period = 3^n -1 (where n=3 since 3 register)

Maximum period = 3^3 -1 =26