Complete the proof that Pr [B inverts y] > 1 by doing the following.

(a) Prove that if y / BAD then Pr B inverts y = 1 2 ^(n) . Deduce that it suffices to show that Pry{0,1}^m [y / BAD] > 1 /2.

(b) Prove that Pr(y1,...,yk){0,1}^mk [A(y1, . . . , yk) wins & i st yi BAD] . Deduce that Pry{0,1}^m [y / BAD]^k .

(c) Complete the proof by showing that if Pry{0,1}^m [y / BAD] 1 /2, then 2 ^n , a contradiction since is non-negligible.