mersenneforum.org Factoring as the problem of quadratic minimization
 Register FAQ Search Today's Posts Mark Forums Read

 2021-06-30, 18:52 #1 tetramur   "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 <= N-1 2 <= x2 <= N-1 x1 <= x2 Question: is it possible to get polynomial-timed solution for this problem?
2021-06-30, 19:09   #2
charybdis

Apr 2020

10358 Posts

Quote:
 Originally Posted by tetramur Minimize x1*x2 with these conditions: x1*x2 >= N 2 <= x1 <= N-1 2 <= x2 <= N-1 x1 <= x2
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 problem in polynomial time.

2021-06-30, 19:42   #3
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×3×11×23 Posts

Quote:
 Originally Posted by tetramur 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.

2021-07-01, 06:11   #4
tetramur

"unknown"
Jan 2019
anywhere

1710 Posts

Quote:
 Originally Posted by R. Gerbicz 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.
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.

 Similar Threads Thread Thread Starter Forum Replies Last Post RedGolpe Factoring 9 2008-09-02 15:27 ShiningArcanine Math 2 2008-04-16 13:47 VolMike Software 5 2007-07-26 13:35 ThiloHarich Factoring 47 2007-01-08 14:12 asdf Puzzles 4 2003-08-30 17:56

All times are UTC. The time now is 09:39.

Sun Nov 28 09:39:46 UTC 2021 up 128 days, 4:08, 0 users, load averages: 1.11, 1.17, 1.08