Question 3 (Repeated Multiplication, 30 points). In class we saw that Karatsuba multiplication allowed one to multiply two n-bit numbers in O(nlo82(3)) time. It turns out that using the Fast Fourier Transform, one can multiply numbers in nearly linear time. For the purposes of this problem, assume that one has an algorithm Mult(N, M) that can multiply two n-bit numbers in O(n) time. ( a) Give an algorithm to multiply k n-bit numbers Ni, N2,..., Nk irn O(klog(k)n) time. [20 points (b) Give an algorithm to compute the kth power of an n-bit number in O(kn) time. [10 points Note: When you multiply two numbers together the length of the resulting number will be the sum of the lengths of the original numbers. This means that you cannot, for example, solve part (a) by simply multiplying the numbers one at a time, since the Eth product will involve en-bit numbers and thus take O(ln) time, making the total runtime O(k2n).]