mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2017-09-14, 04:56   #1
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Gracie on alert.

40010 Posts
Default 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.
jwaltos is offline   Reply With Quote
Old 2017-09-14, 06:27   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

5·7·313 Posts
Default

Quote:
Originally Posted by jwaltos View Post
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 ...
xilman is offline   Reply With Quote
Old 2017-09-14, 07:09   #3
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

628210 Posts
Default

Quote:
Originally Posted by jwaltos View Post
-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
retina is online now   Reply With Quote
Old 2017-09-14, 07:29   #4
S485122
 
S485122's Avatar
 
"Jacob"
Sep 2006
Brussels, Belgium

33208 Posts
Default

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
S485122 is offline   Reply With Quote
Old 2017-09-14, 08:21   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

11000100010102 Posts
Default

It looks not to dissimilar from an elliptic curve.
retina is online now   Reply With Quote
Old 2017-09-14, 12:18   #6
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Gracie on alert.

24·52 Posts
Default

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
jwaltos is offline   Reply With Quote
Old 2017-09-14, 14:18   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

498710 Posts
Default

Quote:
Originally Posted by jwaltos View Post
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
Dr Sardonicus is offline   Reply With Quote
Old 2017-09-14, 16:17   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by jwaltos View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-09-14, 18:02   #9
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Gracie on alert.

24×52 Posts
Default

Quote:
Originally Posted by xilman View Post
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
jwaltos is offline   Reply With Quote
Old 2017-09-14, 20:30   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

135338 Posts
Default

Quote:
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.
I think you've reduced factoring to a problem harder than factoring.
CRGreathouse is offline   Reply With Quote
Old 2017-09-14, 20:42   #11
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·32·83 Posts
Default

Quote:
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

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?
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


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

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


Thu Oct 21 22:21:31 UTC 2021 up 90 days, 16:50, 1 user, load averages: 1.20, 1.14, 1.58

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.