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.

  • $\begingroup$ 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$. $\endgroup$ Dec 7 '12 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.