Decomposing a number N into composite factors (e.g., 2059 2971) is generally u for large values of N. For sone N of specific forms, factoring can actually become quite easy: observing that 10467 2262 -1032, we have via the difference of squares formula to be a hard problem 40467 226 -1032-(226 103) (226103) 123329 ak for One special case of an easily factorable number is when N is a perfect power of some integer base, i.e., N 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 i terms of inte 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 ger arithmetic 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 tha VN N, consider sequentially taking each number a e (1,2,3,... ,N -1,N) and computing a. Stop when either i) a2-N and you have found the square root, or ii) a2 > 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. ) We are effectively searching the set(1,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 a 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 l