2
$\begingroup$

Have there been attempts to factor integers with Linear Programming?

Searching the internet suggests that for Integer Factorization only Number Theoretic algorithms, like sieves, are taken into consideration. On the other hand, Linear Programming is successfully applied to a variety of combinatorial problems, so that should be motivation enough to try to make it also applicable to Integer Factorization.

I have managed to find such a formulation and I would like references to literature, where such formulations and their discussion from the practical and theoretical point of view can be found.

Edit:

  • in view of the feedback I have received, I would like to point out, that the emphasis is on Linear Integer Programming or Linear Programming formulations of the Integer Factorization Problem;
    as a motivation, the fact that ILP is fixed parameter tractable and this publication http://e-ntrasites.univpm.it/Ingegneria/Engine/RAServeFile.php/f/Angelo_Parente.pdf should suffice.

  • The "steam hammer" of general Integer Programming that solves every NP problem, is too heavy weight and references to related publications are not desirable to me.

  • references that are related to the question whether Integer Factorization is in $PTAS$ or $APX$ or any other complexity class, are also welcome.

  • references related to the question whether the integrality gap of the $LP$ formulation of Integer Factorization is small enough to allow cryptographic attacks, are welcome, too.

$\endgroup$
  • 6
    $\begingroup$ While I could imagine that you might have an ILP reformulation, an LP reformulation would be quite a feat... $\endgroup$ – Dima Pasechnik Mar 9 '13 at 17:22
  • $\begingroup$ The LP formulation is essentially the ILP formulation with some additional constraints aiming at reducing the gap between the solution to the relaxed problem and the exact problem; the issue is the same as in solving other combinatorial problems with LP. $\endgroup$ – Manfred Weis Mar 10 '13 at 6:23
  • $\begingroup$ It is easy to formulate any NP problem as an LP (an undergrad exercise), however if the solutions are not restricted to integral solutions it will not solve the original problem but a relaxation of it. The result will not mean anything if you cannot round the solution of LP to a meaningful integral one. $\endgroup$ – Kaveh Dec 30 '13 at 8:31
  • $\begingroup$ And since IP is NP-complete it is also an easy exercise to formulate any NP problem as IP. However the algorithms for IP are exponential time in the worst case and people have tried to various formulations of factoring as IP and studied them. You can try Google to find them. Another thing you can try: try to use your reduction to IP and CPLEX to break RSA factoring challenges. $\endgroup$ – Kaveh Dec 30 '13 at 8:38
  • $\begingroup$ @Kaveh maybe you should have read my reply to Dima's appreciated comment - there I clearly say that the LP formulation need not yield a solution to the factoring problem. $\endgroup$ – Manfred Weis Dec 30 '13 at 11:36
1
$\begingroup$

today I found the following paper, which comes closest to what I had hoped for: http://www.optimization-online.org/DB_FILE/2009/06/2329.pdf

In it incarnations of IP/ILP formulations for certain non-linear integer optimizations can be found, however not one specifically dedicated to the integer factorization problem.

So I supply it as an answer in hope for better/further suggestions.

$\endgroup$
1
$\begingroup$

One relevant paper is Indivisibility and divisibility polytopes by Coppersmith and Lee.

$\endgroup$

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.