Computer Science Department – Rutgers University Spring 2018
CS 205: Final Exam Question 3 – Factor Decomposition 16:198:205
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)∗(226+103) = 123∗329. (1) One special case of an easily factorable number is when N is a perfect power of some integer base, i.e., 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
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) Giventhat1≤
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 for the overall complexity of this search in terms of N.
√
10200 ≈ 100.995, as the fractional part is not 0, N cannot be a perfect square. This, however, requires
N≤N,considersequentiallytakingeachnumbera∈{1,2,3,…,N−1,N}andcomputing
4) We are effectively searching the set {1, 2, 3, . . . , N − 1, N} for the value √√
N. For a given a, we can’t compare a to N since we don’t know N. 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) SimilartoQuestions3,4above,giventhat1≤N1/k ≤N,wemayconsidersearchingthesequence{1,2,3,…,N− 1,N} for N1/k. For a given a, we may compare ak to N to determine if we are too high or too low. 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.
7) Questions 5, 6 above assumed that k was known. What if k is unknown? If N is a perfect (non-trivial) power, what is the smallest possible value of k that power might be? What is the largest? Give a big-O bound on the largest possible k.
8) Consider repeating the algorithm in Question 6, for every k over the indicated range above, to search all possible powers to see if N = ak for some a, k. 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 efficient?
1
Computer Science Department – Rutgers University Spring 2018
Bonus
9) The approach outlined above suggested a binary search for the base a for any given k, but utilizes a sequential search for the correct value of k. Could a binary search be utilized to find k as well?
10) Can you come up with a better algorithm for checking if N is a perfect (non-trivial) power?
11) Consider modifying the problem so that instead of finding a,k such that N = ak, you are given a large prime number P and asked to find a, k such that N ≡ ak mod P . What must change in the above approach? Try to outline an algorithm for this problem, given N,P, and given a big-O bound on its complexity. Note, operating mod P, you may assume all multiplications take constant time.
2