mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-06-30, 18:52   #1
tetramur
 
"unknown"
Jan 2019
anywhere

17 Posts
Default 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?
tetramur is offline   Reply With Quote
Old 2021-06-30, 19:09   #2
charybdis
 
charybdis's Avatar
 
Apr 2020

2·251 Posts
Default

Quote:
Originally Posted by tetramur View Post
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.
charybdis is offline   Reply With Quote
Old 2021-06-30, 19:42   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·32·83 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
Old 2021-07-01, 06:11   #4
tetramur
 
"unknown"
Jan 2019
anywhere

1710 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring problem RedGolpe Factoring 9 2008-09-02 15:27
Energy Minimization ShiningArcanine Math 2 2008-04-16 13:47
Problem with P-1 factoring... VolMike Software 5 2007-07-26 13:35
Factoring in the Quadratic Sieve ThiloHarich Factoring 47 2007-01-08 14:12
Factoring Problem asdf Puzzles 4 2003-08-30 17:56

All times are UTC. The time now is 05:33.


Mon Oct 25 05:33:56 UTC 2021 up 94 days, 2 mins, 0 users, load averages: 1.15, 1.00, 1.04

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.