Timeline for Reference Request for Integer factorization with LP/ILP
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 17, 2021 at 12:28 | answer | added | Leonid | timeline score: 1 | |
| Apr 24, 2018 at 0:53 | answer | added | Timothy Chow | timeline score: 1 | |
| Sep 2, 2016 at 14:15 | comment | added | Manfred Weis | Just some linear and boolean algebra; actually not too difficult if you have the right ideas. | |
| Sep 2, 2016 at 3:51 | comment | added | Sidharth Ghoshal | How were you able to encode the multiplication without effectively encoding the multiplication circuit itself? | |
| Sep 2, 2016 at 3:42 | comment | added | Manfred Weis | @frogeyedpeas yes I die; my idea is to express integer multiplication directly (on basis of binary digits) as an ILP; the number of variables would be much less. | |
| Sep 1, 2016 at 17:39 | comment | added | Sidharth Ghoshal | I found that even for say 100 digit numbers, solving via 0-1 IP requires on the order of 100,000 variables, and close to a million constraints | |
| Sep 1, 2016 at 17:38 | comment | added | Sidharth Ghoshal | @ManfredWeis did you find any conversions of factoring to 0-1IP, that are more efficient than the classical reduction of factoring->CircuitSAT->0-1IP? | |
| Jan 4, 2014 at 16:23 | history | edited | Manfred Weis | CC BY-SA 3.0 |
Added clarification on the kind of desired references
|
| Jan 2, 2014 at 10:54 | answer | added | Manfred Weis | timeline score: 1 | |
| Jan 2, 2014 at 8:14 | comment | added | Manfred Weis | The currently best reference to the complexity of ILP I found, is cstheory.stackexchange.com/questions/16530/…, however no ILP formulation for integer factorization is given; at least it allows it to estimate the complexity for a fixed number of bits. | |
| Dec 30, 2013 at 17:00 | review | Close votes | |||
| Dec 31, 2013 at 12:22 | |||||
| Dec 30, 2013 at 11:36 | comment | added | Manfred Weis | @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. | |
| Dec 30, 2013 at 8:38 | comment | added | Kaveh | 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. | |
| Dec 30, 2013 at 8:31 | comment | added | Kaveh | 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. | |
| Nov 5, 2013 at 20:46 | review | Close votes | |||
| Nov 6, 2013 at 13:04 | |||||
| Jul 28, 2013 at 17:36 | history | edited | Manfred Weis | CC BY-SA 3.0 |
reformulated my request and added the reference tag.
|
| Mar 10, 2013 at 6:23 | comment | added | Manfred Weis | 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. | |
| Mar 9, 2013 at 17:22 | comment | added | Dima Pasechnik | While I could imagine that you might have an ILP reformulation, an LP reformulation would be quite a feat... | |
| Mar 9, 2013 at 16:46 | history | asked | Manfred Weis | CC BY-SA 3.0 |