Problem 2 [40 pts] Solve Problem 1.32 from the textbook. Remember that we analyze algorithms for thier bit complexity and therefore analysis must be based on the number of bits taken to represent the number in question. An algorithm not polynomial in the input size will not be considered efficient.

1.32. A positive integer N is a power if it is of the form qk, where q, k are positive integers and k > 1. (a) Give an efficient algorithm that takes as input a number N and determines whether it is a square, that is, whether it can be written as q2 for some positive integer q. What is the running time of your algorithm? (b) Show that if N =qk (with N, q, and k all positive integers), then either k