# How can P =? NP enhance integer factorization

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?

-

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).

-

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.

-
just to clarify for OP: the common decision version of factoring is "does the number $X$ have a factor $Y$ such that $1 < Y < K$", where $X$ and $K$ are input. the certificate is simply a number $Y$ satisfying the condition. the decision problem can be used to actually factor by doing a binary search on $K$ until a single proper factor of $X$ is found and then recurse on $X / Y$. – Sasho Nikolov Dec 7 '12 at 0:20