Decomposing a number N into composite factors (e.g., 2059-29 *71) is generally understood to be a hard problem for large values of N. For some N of specific forms, factoring can actually become quite easy; observing that 40467 2262-1032, we have via the difference of squares formula 40467 2262 -1032(226 103) (226103) 123 329 One special case of an easily factorable number is when N is a perfect power of some integer base, ie., N = ak for some integer a, k > 1. Consider the question, "is N = 10200 a perfect square?" One way to check might be to compute the square root Since v10200100.995, as the fractional part is not 0, N cannot be a perfect square. This, however, requires computation over the real numbers, a topic largely untouched in this course. The goal of this problem is to approach this computation, purely in terms of integer arithmetic In each of the following, when we ask for a big-O bound, we are interested in as tight an upper bound as you can justify 1) Give a big-O bound for the number of bits needed to represent a number N 2) Give a big-O bound for the bit-complexity of multiplying two integers between 1 and N. What is the worst case? Note, the bound should be simply in terms of N 3) Given that 1 N and N does not have an integer square root. Give a big-O bound for the overall complexity of this search in terms of N 4) We are effectively searching the set f1,2,3,... ,N - 1,N} for the value VN. For a given a, we can't compare a to VN since we don't know VN. However, we can compare a2 to N. Use this idea as the basis of a binary search-type algorithm. Give a big-O bound on the overall complexity of this search in terms of N. How does it compare to the previous? 5) Given an integer k> 1, give a big-O bound for the bit-complexity of computing the k-th power of an integer between 1 and N. What is the worst case? Note that the bound should be in terms of N and k 6) Similar to Questions 3, 4 above, given that 1