Show that if P = NP, you can factor integers in polynomial time. (See the note in Problem 7.38.)

Problem 7.38.

Show that if P = NP, a polynomial time algorithm exists that produces a satisfying assignment when given a satisfiable Boolean formula. Note: The algorithm you are asked to provide computes a function; but NP contains languages, not functions. The P = NP assumption implies that SAT is in P, so testing satisfiability is solvable in polynomial time. But the assumption doesn’t say how this test is done, and the testmay not reveal satisfying assignments. Youmust show that you can find them anyway. Hint: Use the satisfiability tester repeatedly to find the assignment bit-by-bit.