Book Cryptology Theory and Practice 3rd Edition Page 40 Pro

Book: Cryptology - Theory and Practice (3rd Edition) Page: 40 Problem: 1.18 and 1.19 1.18 Consider the following linear recurrence over Z2 of degree four: zi+4 = (zi + zi+1 + zi+2 + zi+3) mod 2, i > = 0. For each of the 16 possible initialization vectors (z0, z1, z2, z3) E (Z2)^4, determine the period of the resulting keystream. 1.19 Redo the preceding question, using the recurrence zi+4 = (zi + zi+3) mod 2, i > = 0.

Solution

I am solving the problem 18, please post one problem as a problem from next time. Thanks,Nikhil

Since there are four vectors which can take value i.e. (0,1)

Hence number of combinations will be 2^(4) = 16 vectors starting from (0,0,0,0) to (1,1,1,1)

(0,0,0,0) -> zvalue = (0+0+0+0)mod2 = 0 mod 2 = 0

(0,0,0,1) -> zvalue = (0+0+0+1)mod2 = 1 mod 2 = 1

(0,0,1,0) -> zvalue = (0+0+1+0)mod2 = 1 mod 2 = 1

(0,0,1,1) -> zvalue = (0+0+1+1)mod2 = 2 mod 2 = 0

(0,1,0,0) -> zvalue = (0+1+0+0)mod2 = 1 mod 2 = 1

(0,1,0,1) -> zvalue = (0+1+0+1)mod2 = 2 mod 2 = 0

(0,1,1,0) -> zvalue = (0+1+1+0)mod2 = 2 mod 2 = 0

(0,1,1,1) -> zvalue = (0+1+1+1)mod2 = 3 mod 2 = 1

(1,0,0,0) -> zvalue = (1+0+0+0)mod2 = 1 mod 2 = 1

(1,0,0,1) -> zvalue = (1+0+0+1)mod2 = 2 mod 2 = 0

(1,0,1,0) -> zvalue = (1+0+1+0)mod2 = 2 mod 2 = 0

(1,0,1,1) -> zvalue = (1+0+1+1)mod2 = 3 mod 2 = 1

(1,1,0,0) -> zvalue = (1+1+0+0)mod2 = 2 mod 2 = 0

(1,1,0,1) -> zvalue = (1+1+0+1)mod2 = 3 mod 2 = 1

(1,1,1,0) -> zvalue = (1+1+1+0)mod2 = 3 mod 2 = 1

(1,1,1,1) -> zvalue = (1+1+1+1)mod2 = 4 mod 2 = 0

The period implies

z(i+d) = z(i), where i can be any number

For the following linear recurrence, the value will be going to definetly repeated after every 4 iterations Hence the period is equal to 4