View Single Post
Old 2021-06-30, 19:42   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

72·31 Posts
Default

Quote:
Originally Posted by tetramur View Post
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?
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.
R. Gerbicz is offline   Reply With Quote