LetG:{0,1}ⁿ{0,1}^l(n) be an algorithm which takes s=s1s2sn{0,1}ⁿas input and outputs G(s) =s1sns2sn1s3sn2sns1.

For example,G(10) = 1001,G(110) =101101.

(a) Find the expansion factor l(n).

(b) One efficient distinguisher D that claims G is not a pseudorandom generator is the following: For w l(n),D(w) = 1if the first and last bits are equal, and D(w) = 0 otherwise.Find another efficient distinguisher D that claims G is not a pseudorandom generator.

(c) Using the distinguisher you obtained in part (b), find the value of

| Pr_s{0,1}ⁿ D(G(s))Pr_r{0,1}^l(n) D(r) |

and conclude that G is not pseudorandom.