Question

Show that if $\mathit{P}\mathbf{=}\mathit{N}\mathit{P}$ , you can factor integers in polynomial time. (See the note in Problem 7.38.)

Short answer

It can identify that all of the factors in polynomial time since there are only $O\left(k\right)$ factors (the maximum number of factors that can occur when $n$ is simply a product of 2s).

Step-by-step solution

Step-1: Polynomial Time

If the running time of an algorithm is upper constrained by a polynomial expression in the size of the method's input, the algorithm is said to be polynomial time.

Step-2: Range of the polynomial time

Let language is represented as:

$L=\left\{\left(n,a,b\right)|nhasafactorpintherangea⩽p⩽b\right\}$$L$is obviously in $NP$, because the factor can act as a certificate. Because it is assuming that $P=NP$, there's a polynomial method that determines the result. Using the method multiple times allows to divide search space.

"Is there a factor in the range $\left(a,a+b/2\right)?$"In this it can represent that there's a factor in the other range if there isn't one.If $k$ is the number of bits in $n$, the total number of times apply the algorithm is $\log n$, or $O\left(k\right)$. As a result, it may isolate one factor with a polynomial number of executions of this technique.