- **Factoring**
(*https://www.mersenneforum.org/forumdisplay.php?f=19*)

- - **Factoring as the problem of quadratic minimization**
(*https://www.mersenneforum.org/showthread.php?t=26966*)

Factoring as the problem of quadratic minimizationThe factoring is trivially equivalent to following minimization problem:
Minimize x1*x2 with these conditions: x1*x2 >= N 2 <= x1 <= N-1 2 <= x2 <= N-1 x1 <= x2 Question: is it possible to get polynomial-timed solution for this problem? |

[QUOTE=tetramur;582328]Minimize x1*x2 with these conditions:
x1*x2 >= N 2 <= x1 <= N-1 2 <= x2 <= N-1 x1 <= x2[/QUOTE] Okay, let's try this. Suppose I want to factorize N = 91. I'll plug your conditions into my magic optimization machine, and out come the factors: x1 = √91, x2 = √91 Wait, you wanted the solutions to be integers? Well, you're out of luck - my machine doesn't know how to solve that type of [URL="https://en.wikipedia.org/wiki/Integer_programming"]problem[/URL] in polynomial time. |

[QUOTE=tetramur;582328]The factoring is trivially equivalent to following minimization problem:
Minimize x1*x2 with these conditions: x1*x2 >= N 2 <= x1 <= N-1 2 <= x2 <= N-1 x1 <= x2 Question: is it possible to get polynomial-timed solution for this problem?[/QUOTE] No, you need also that x1 and x2 are integers(!), and with this it is an integer optimization problem [without easy 'shortcuts"], you can try it out using say GLPK (it is free). And it is quite well known. Another similar form: minimize 0 subject to: x1 and x2 are integers x1*x2=N 2<=x1 2<=x2 ps. note that if N is prime then this form has no solution. |

[QUOTE=R. Gerbicz;582334]No, you need also that x1 and x2 are integers(!), and with this it is an integer optimization problem [without easy 'shortcuts"], you can try it out using say GLPK (it is free). And it is quite well known. Another similar form:
minimize 0 subject to: x1 and x2 are integers x1*x2=N 2<=x1 2<=x2 ps. note that if N is prime then this form has no solution.[/QUOTE] Yes, exactly. I intended solution to be integers. Also, I checked that integer optimization problems are NP-complete in general, but I don't know if this particular problem is NP-complete. |

All times are UTC. The time now is 23:54. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.