 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Homework Help (https://www.mersenneforum.org/forumdisplay.php?f=78)
-   -   Is this solvable in general. (https://www.mersenneforum.org/showthread.php?t=22578)

 jwaltos 2017-09-14 04:56

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.

 xilman 2017-09-14 06:27

[QUOTE=jwaltos;467756]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.[/QUOTE]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 ...

 retina 2017-09-14 07:09

[QUOTE=jwaltos;467756]-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.[/QUOTE]You can replace x and y with any value you like. Simplifying and coalescing all the constants gives this [b]formula[/b]:

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

 S485122 2017-09-14 07:29

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[/quote]

Jacob

 retina 2017-09-14 08:21

It looks not to dissimilar from an elliptic curve.

 jwaltos 2017-09-14 12:18

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...

 Dr Sardonicus 2017-09-14 14:18

[QUOTE=jwaltos;467756]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.[/QUOTE]
I second [b]xilman[/b]'s question, where did this function come from?

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

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

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

 CRGreathouse 2017-09-14 16:17

[QUOTE=jwaltos;467769]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.[/QUOTE]

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.

 jwaltos 2017-09-14 18:02

[QUOTE=xilman;467758]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 ...[/QUOTE]

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.

 CRGreathouse 2017-09-14 20:30

[QUOTE=jwaltos;467787]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.[/QUOTE]

I think you've reduced factoring to a problem harder than factoring. :unsure:

 R. Gerbicz 2017-09-14 20:42

[QUOTE=jwaltos;467787]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.[/QUOTE]

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
[/CODE]
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?

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