mersenneforum.org Is this solvable in general.
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2017-09-14, 04:56 #1 jwaltos     Apr 2012 Gracie on lookout. 2×11×19 Posts Is this solvable in general. Soliciting advice on how to solve this equation: -2*x^3+(19/2-60*a-60*b*y)*x^2+(21/2+314*a+30*d*y+30*c+314*b*y)*x+2+205*a+11*c+900*b*y*c+420*a*b*y+210*a^2+210*b^2*y^2+11*d*y+900*a*d*y+900*b*y^2*d+205*b*y+900*a*c Assuming a, b, c and d are known, what is the best method to resolve the remaining variables: x, y, such that the resulting number is a specific integer.
2017-09-14, 06:27   #2
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2·3·17·109 Posts

Quote:
 Originally Posted by jwaltos Soliciting advice on how to solve this equation: -2*x^3+(19/2-60*a-60*b*y)*x^2+(21/2+314*a+30*d*y+30*c+314*b*y)*x+2+205*a+11*c+900*b*y*c+420*a*b*y+210*a^2+210*b^2*y^2+11*d*y+900*a*d*y+900*b*y^2*d+205*b*y+900*a*c Assuming a, b, c and d are known, what is the best method to resolve the remaining variables: x, y, such that the resulting number is a specific integer.
Where does this come from? It's far too complicated for it to be at all likely that you made it up on the spur of the moment so it likely arises in the course of some other algebraic manipulations. Knowing its origin could well make a solution easier to find.

BTW, it's not an equation (I don't see a '=' anywhere within it) but a formula. Someone has to do RDS's job for him these days ...

2017-09-14, 07:09   #3
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

22·3·17·31 Posts

Quote:
 Originally Posted by jwaltos -2*x^3+(19/2-60*a-60*b*y)*x^2+(21/2+314*a+30*d*y+30*c+314*b*y)*x+2+205*a+11*c+900*b*y*c+420*a*b*y+210*a^2+210*b^2*y^2+11*d*y+900*a*d*y+900*b*y^2*d+205*b*y+900*a*c Assuming a, b, c and d are known, what is the best method to resolve the remaining variables: x, y, such that the resulting number is a specific integer.
You can replace x and y with any value you like. Simplifying and coalescing all the constants gives this formula:

f(x,y) = a*x^3 + (b+c*y)*x^2 + (d+e*y)*x + f*y^2 + g*y + h

Last fiddled with by retina on 2017-09-14 at 07:10

2017-09-14, 07:29   #4
S485122

"Jacob"
Sep 2006
Brussels, Belgium

177410 Posts

You both forgot the last part of the question : "such that the resulting number is a specific integer."

Rephrasing a bit
Quote:
 Assuming a, b, c and d are known, what is the best method to resolve the remaining variables: x, y in order that the formula yields a specific integer A when A=-2*x^3+(19/2-60*a-60*b*y)*x^2+(21/2+314*a+30*d*y+30*c+314*b*y)*x+2+205*a+11*c+900*b*y*c+420*a*b*y+210*a^2+210*b^2*y^2+11*d*y+900*a*d*y+900*b*y^2*d+205*b*y+900*a*c
Jacob

 2017-09-14, 08:21 #5 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 22·3·17·31 Posts It looks not to dissimilar from an elliptic curve.
 2017-09-14, 12:18 #6 jwaltos     Apr 2012 Gracie on lookout. 2·11·19 Posts Thank you for the responses. I developed this equation as part of an integer factorization toolkit. Complex and rational values apply to a,b,c,d,x,y which can also resolve this equation to an integer value. I can solve for the a,b,c,d values in a deterministic manner but resolving x,y for large values of F in polynomial time still evades me. I am somewhat stymied and vexed regarding how to solve this equation without using sieving or random processes for large values. Transformations into polar coordinates, complex analysis and differential geometry are valid solution paths. A suitable selection for the values a,b,c,d,x will algebraically factor the equivalence into (m*y+c1)*(n*y+c2). ie. a=0:b=1:c=35:d=40:x=1 -->(17*y+15)*(2130*y+97) F=-2*x^3+(19/2-60*a-60*b*y)*x^2+(21/2+314*a+30*d*y+30*c+314*b*y)*x+2+205*a+11*c+900*b*y*c+420*a*b*y+210*a^2+210*b^2*y^2+11*d*y+900*a*d*y+900*b*y^2*d+205*b*y+900*a*c where F can be any integer. Basically, my question is, what are the least number of variables within this equation that must be known and what are their numeric limits before it cannot be solved in polynomial time. Conversely, what must be known before this equation can be solved in polynomial time and what tools are required. ie LLL, infinite precision, etc... Last fiddled with by jwaltos on 2017-09-14 at 12:47 Reason: clarification
2017-09-14, 14:18   #7
Dr Sardonicus

Feb 2017
Nowhere

14DA16 Posts

Quote:
 Originally Posted by jwaltos Soliciting advice on how to solve this equation: -2*x^3+(19/2-60*a-60*b*y)*x^2+(21/2+314*a+30*d*y+30*c+314*b*y)*x+2+205*a+11*c+900*b*y*c+420*a*b*y+210*a^2+210*b^2*y^2+11*d*y+900*a*d*y+900*b*y^2*d+205*b*y+900*a*c Assuming a, b, c and d are known, what is the best method to resolve the remaining variables: x, y, such that the resulting number is a specific integer.
I second xilman's question, where did this function come from?

I'll call it F(a,b,c,d,x,y)

Knowing what kind of critter this is, would be of considerable help in addressing the question of solving

F(a,b,c,d,x,y) = N

2017-09-14, 16:17   #8
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by jwaltos Basically, my question is, what are the least number of variables within this equation that must be known and what are their numeric limits before it cannot be solved in polynomial time.
You're asking about a bivariate Diophantine cubic equation. But even bivariate Diophantine quadratics generally take more than polynomial time, so I see no reason to be that optimistic.

2017-09-14, 18:02   #9
jwaltos

Apr 2012
Gracie on lookout.

1101000102 Posts

Quote:
 Originally Posted by xilman Where does this come from? It's far too complicated for it to be at all likely that you made it up on the spur of the moment so it likely arises in the course of some other algebraic manipulations. Knowing its origin could well make a solution easier to find. BTW, it's not an equation (I don't see a '=' anywhere within it) but a formula. Someone has to do RDS's job for him these days ...
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.

Last fiddled with by jwaltos on 2017-09-14 at 18:14

2017-09-14, 20:30   #10
CRGreathouse

Aug 2006

3×1,993 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.
I think you've reduced factoring to a problem harder than factoring.

2017-09-14, 20:42   #11
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

101111110102 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?

 Similar Threads Thread Thread Starter Forum Replies Last Post pastcow Factoring 10 2013-02-27 07:01 R.D. Silverman NFSNET Discussion 4 2007-07-19 18:43 pacionet Miscellaneous Math 15 2005-12-08 08:00 Val 15k Search 10 2004-03-13 20:56 TTn Miscellaneous Math 1 2003-08-26 03:14

All times are UTC. The time now is 22:01.

Mon Jan 17 22:01:32 UTC 2022 up 178 days, 16:30, 0 users, load averages: 1.35, 1.36, 1.26

Copyright ©2000 - 2022, 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.

โ  ยฑ โ รท ร ยท โ โ โฐ โ โ โ โ โ โค โฅ โฆ โง โจ โฉ โบ โป โผ โฝ โ โ โ โ ยฒ ยณ ยฐ
โ  โ ยฐ โ ~ โ โ โซ
โก โ โ โ โ โช โซ โโ โโ โ โ โ โ โง โจ โฉ โช โจ โ โ ๐ ๐ ๐ โฒ โณ
โ โ โ โฆ โฃ โฉ โช โ โ โ โ โ โ โ โ โ โ โ โ โ โ โค โ โ โ โต โถ โท โธ ๐
ยฌ โจ โง โ โ โ โ โ โ โ โ โ โด โต โค โฅ โข โจ โซค โฃ โฆ โฏ โฎ โฐ โฑ
โซ โฌ โญ โฎ โฏ โฐ โ โ ฮด โ โฑ โ โ
๐ข๐ผ ๐ฃ๐ฝ ๐ค๐พ ๐ฅ๐ฟ ๐ฆ๐๐ ๐ง๐ ๐จ๐ ๐ฉ๐๐ ๐ช๐ ๐ซ๐ ๐ฌ๐ ๐ญ๐ ๐ฎ๐ ๐ฏ๐ ๐ฐ๐ ๐ฑ๐ ๐ฒ๐ ๐ด๐ ๐ต๐ ๐ถ๐ ๐ท๐๐ ๐ธ๐ ๐น๐ ๐บ๐