How can P =? NP enhance integer factorization

Question

If ${\sf P}$ does in fact equal ${\sf NP}$, how would this enhance our algorithms to factor integers faster. In other words, what kind of insight would this fact give us in understanding integer factorization better?

Answer 1

If $P=NP$, and we have an algorithm that can solve the k-SAT problem in polynomial time, then integer factorization can simply be reduced to k-SAT by describing factoring as a problem in k-SAT.

Essentially it works as follows: You make a bunch of variables each representing the bits of $p$, and $q$, and $n$. Then you formulate the k-SAT problem as $p*q=n$. Since $n$ is known, you can set those values. Then a satisfying assignment will describe a valid $p$ and $q$. To describe the multiplication in k-SAT, you can use any of the known multiplication algorithms and describe it's logical circuit in k-SAT. For more info on reducing factoring to k-SAT, see here.

As for understanding factoring better, that would probably require more research and analyzing the magic algorithm (that can solve NP-complete problems in deterministic polynomial time), and perhaps specializing it to the integer-factoring formulation of k-SAT problem (which obviously has a very specific structure, depending on the multiplication algorithm used).

Answer 2

The decision problem for factoring is $\mathsf{NP}$ and the factoring can be reduced to it in deterministic polynomial time.

If $\mathsf{P}=\mathsf{NP}$ then then any problem in $\mathsf{NP}$ including factoring will have a polynomial time algorithm.

Note that the best known deterministic/probabilistic algorithms for factoring at the moment take exponential time so a polynomial time algorithm would be a great improvement. To get a feeling of it, consider factoring a 2000 bit number. One may take longer than all the time since the big bang, the other may answer in a few milliseconds.