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.

Improve this question
$\endgroup$
11
  • 7
    $\begingroup$ While I could imagine that you might have an ILP reformulation, an LP reformulation would be quite a feat... $\endgroup$
    – Dima Pasechnik
    Commented Mar 9, 2013 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
    Commented Mar 10, 2013 at 6:23
  • 1
    $\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
    Commented Dec 30, 2013 at 8:31
  • 1
    $\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
    Commented Dec 30, 2013 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
    Commented Dec 30, 2013 at 11:36

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

Factoring as Optimization could be a useful link in this direction as well.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Welcome to MO and thanks for posting! Please consider adding some additional details about the contents of the link, as link-only answers can quickly become outdated if links change. $\endgroup$
    – gmvh
    Commented Apr 17, 2021 at 12:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .