Problem 2 (Integer multiplication using FFT)

(a) Given an nbit integer number a = a0a1a2 . . . an1 define a polynomial A(x) satisfying A(2) = a.

(b) Given two nbit integers a and b, give an algorithm to multiply them in O(nlog(n)) time. Use the FFT algorithm from class as a black-box (i.e. dont rewrite the code, just say run FFT on ...).Explain your algorithm in words and analyse its running time.