20210630, 18:52  #1 
"unknown"
Jan 2019
anywhere
17 Posts 
Factoring as the problem of quadratic minimization
The factoring is trivially equivalent to following minimization problem:
Minimize x1*x2 with these conditions: x1*x2 >= N 2 <= x1 <= N1 2 <= x2 <= N1 x1 <= x2 Question: is it possible to get polynomialtimed solution for this problem? 
20210630, 19:09  #2  
Apr 2020
2·251 Posts 
Quote:
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 problem in polynomial time. 

20210630, 19:42  #3  
"Robert Gerbicz"
Oct 2005
Hungary
2·3^{2}·83 Posts 
Quote:
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. 

20210701, 06:11  #4  
"unknown"
Jan 2019
anywhere
17_{10} Posts 
Quote:
Also, I checked that integer optimization problems are NPcomplete in general, but I don't know if this particular problem is NPcomplete. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring problem  RedGolpe  Factoring  9  20080902 15:27 
Energy Minimization  ShiningArcanine  Math  2  20080416 13:47 
Problem with P1 factoring...  VolMike  Software  5  20070726 13:35 
Factoring in the Quadratic Sieve  ThiloHarich  Factoring  47  20070108 14:12 
Factoring Problem  asdf  Puzzles  4  20030830 17:56 