Final Question 2: Detecting Perfect Powers Solution

Consider the problem of factoring - decomposing a number N into its composite factors, (e.g., 2881 = 67 43). This is generally understood to be a hard problem (in that the di culty increases rapidly with N). For some N however, factoring can actually be quite straightforward (consider numbers that end in a digit 5, or numbers that are the di erence of two squares). One special case of easily factorable numbers: N that are perfect powers, i.e., N = ak for some integer a; k 1. The purpose of this question is to analyze the following problem: i) given an integer N, what is the complexity of determining if N is a perfect power, and ii) if N is a perfect power, what the values of a and k are such that N = ak? The main observation is that while computing roots (how do you compute a square root?) is di cult, computing powers and exponentiating can actually be quite easy.




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.




Give a big-O bound on the number of bits needed to represent a number N. (2 points)



Give a big-O bound on the complexity of multiplying two integers between 1 and N? Hint: what is the worst case? Note, the bound should be simply in terms of N. (3 points)



Given N, k, what is the big-O complexity of computing Nk? Hint: Consider fast exponentiation. Note, the bound should be in terms of N and k. (5 points)



Consider the problem rst of determining whether or not N is a perfect square:






p








4)
Given that 1N N, consider sequentially taking each number a 2 f1; 2; 3; : : : ; N 1; Ng and computing


a2. 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 on the overall complexity of this search in terms of N. (4 points)


As an alternate approach: we are e ectively searching the set f1; 2; 3; : : : ; Ng for the value of p


if it is there.
5)
N
p p




For a given a, we can’t compare a to N since N is not known. However, we can compute and 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? (6 points)




Generalize this idea then to determining whether or not N is a perfect k-th power for some given k (take k to be known):




6) Given that 1 N1=k N, consider sequentially taking each number a 2 f1; 2; 3; : : : ; N 1; Ng and computing ak. Stop when either i) ak = N and you have found the k-th root, or ii) ak N and N does not have an integer k-th root. Give a big-O bound on the overall complexity of this search in terms of N and k. (4 points)




As an alternate approach: we are e ectively searching the set f1; 2; 3; : : : ; Ng for the value of N1=k if it is there. For a given a, we can’t compare a to N1=k since N1=k is not known. However, we can compute and compare ak 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 and k. How does it compare to the previous? (6 points)



However, we may not know what exponent k to look for - k may be unknown, and need to be determined:




For a given value of N, what is the smallest value of k that may need to be considered? What is the largest value of k? Give a big-O bound on the largest possible k. (5 points)






1
Computer Science Department - Rutgers University Fall 2018







Consider extending the algorithm in Question 7 in the following way: for every possible k over the range above,



use the algorithm in Question 7 to determine if N is a perfect k-power. If it is found that N = ak for some a; k, report them, otherwise report that N is not a perfect power. For clarity, write out the pseudocode of this algorithm given an input N. Give a big-O bound on the overall complexity of this search, in terms of N. Is this e cient? (15 points)




Bonus: What if we wanted to know if N was a perfect power mod some prime P . Could this algorithm still be used?




Bonus 2: The above suggested a linear search over possible values of k. Could this be improved, and if so, how? In the case of a linear search, would it be better to try k smallest to largest, or largest to smallest?





























































































































































2