View Single Post
Old 2017-09-14, 20:42   #11
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

1,493 Posts

Originally Posted by jwaltos View Post
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

min x+y
subject to
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?
R. Gerbicz is offline   Reply With Quote