Thread: Is this solvable in general. View Single Post
2017-09-14, 20:42   #11
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,493 Posts

Quote:
 Originally Posted by jwaltos This equation was derived in my attempts to develop a simple method of factoring integers that can be done in polynomial time without the use of quantum based systems OR to determine that the IFP cannot be resolved in poly time. Some of the literature I have cited in prior posts as well as member posts have contributed to the origin of that expression. It's a simple representative result. By relaxing the condition in Matiyasevich's theorem for integer only solutions, Le Chatelier's principle could be invoked (by analogy) where poly time solutions can be made explicit. And yes, like a blind squirrel searching for nuts, optimism does help but having a nose for certain things prevents that squirrel from starving. I can't elaborate more without redundancy so I'll just say thanks to those who submitted their input and keep beavering away at this.
I'd say you are overcomplicating this. We can reformulate the factorization problem with a non-linear integer optimization problem: for a given n>1 integer write

Code:
min x+y
subject to
x*y=n
x>=0
y>=0
x,y is integer
then n is prime iff the opt=n+1, otherwise n is composite and we'll know a non-trivial factor of n. With this if the above problem is solvable in polynomial time then integer factorization problem is also in poly. (just call it also recursively for the d,n/d factor where d=x).

Using this in some case any solution will give a non trivial factorization, say for
(5*x+2)*(5*y+2)=n. (it'll give a solution if n=4 mod 5 and n has a d=2 mod 5 divisor). Why would be your longer and higher/ degree polynom is easier than mine?