Project Lovecraft Problem 1

[danbaron]

Problem 1:

Find the integer values of V, W, X, Y, and Z, such that the following five equations
are simultaneously satisfied.

V^22 + W^16 + X^12 + Y^08 + Z^03 = 002502992329277899

V^24 + W^20 + X^14 + Y^06 + Z^05 = 243157986743736595

V^25 + W^17 + X^15 + Y^07 + Z^02 = 349440572700196373

V^21 + W^19 + X^13 + Y^10 + Z^01 = 187066077815684081

V^23 + W^18 + X^11 + Y^09 + Z^04 = 010291125672405119

DTB.

[kryton9]

I'm not a math person, but in one of the thinBasic Journals, Petr had an article on Matrices that seemed to solve stuff like this. I made a note in my mind about it in case I ever feel bright and can understand it and put it to use one day.

http://community.thinbasic.com/index.php?topic=2310.0

[danbaron]

I just downloaded the journal, Kent.

The article is about solving linear equations.

The ones in the problem, are nonlinear.

I'm going to change the problem, anyway.

After you make something, you always think of ways to improve it, right?

(I didn't know there was a thinBasic Journal.)

Dan

[kryton9]

It's been a long time since Math at school for me. Now I will have to look up the difference between linear and non linear problems, which is nice. Always good to learn something new. I am sure Petr, being the math and computer whiz that he is, will be able to help you when sees this post.

[Petr Schreiber]

Hi,

the first thing which occurred to me was the matrix approach, like Kent said. Then I discovered those naughty "^" and currently I am a bit lost. Except brute force, no smart solution does occur to me now. Will think about it more :]

[danbaron]

I changed the problem in an attempt to discourage use of the brute force method.

3*x + 2*y = 6 is linear, because its plot is a straight line,

y = 3 - 3*x/2.

x^3 + y^2 = 6 is nonlinear, because its plot is curved,

y = +- Sqrt(6 - x^3).

The same reasoning applies to dimensions higher than two.

Systems of nonlinear equations are harder to solve than systems of linear equations.

I think that, depending on the problem, there is no method that is guaranteed to work.

I was looking at the Crypto module.

I looked up "Rijndael" at Wikipedia.

I also read about so-called "one way functions".

I think that this problem could be viewed as an example of a one way function.

It is easy to construct, I know the answers, but maybe it is not so easy to solve.

Anyway, it is just for fun.

Dan

[zak]

hi
i have tried www.wolframalpha.com on your x^3 + y^2 = 6 example
like this
solve x^3 + y^2 = 6 over the integers
and it succeed in the answer as the picture below:

http://img718.imageshack.us/img718/3245/mathy.jpg

but i can't make it to solve your first complex equations, i don't know how to write the scheme on a one line. it seems there is a long road until wolframalpha to be a startrek computer.
regards

[Charles Pegge]

Hi Dan,

Have you tried solving a problem similar to yours above ?

This is verging on cryptography. Might stand a chance of solving it visually if we can get hold of some 4D graph paper. :D

Charles

[ErosOlmi]

4D :?:

I was thinking about a 5D TBGL script :comp12:

[Michael Hartlef]

You guys are all crazy :excited: I regret not learning more math. :unguee:

[ErosOlmi]

Dan,

tell us all the truth :D
You have created a set of crypto keys and you are trying to test if someone will breack them ?

I've created a brute force application but after some preliminar tests the conclusion is that my computer will take some (weel, many) years to find the solution.
:unguee:

Eros

[ErosOlmi]

Maybe using wolframalpha and successive substitution ...

For example first equation is solved in the following way:
http://www.wolframalpha.com/input/?i=solve+V%5E22+%2B+W%5E16+%2B+X%5E12+%2B+Y%5E08+%2B+Z%5E03+%3D+002502992329277899

So we got Z value.
Substitute Z value in second equation with the above result and you should get Y value:
http://www.wolframalpha.com/input/?i=V%5E24%2B%28-V%5E22-W%5E16-X%5E12-Y%5E8%2B2502992329277899%29%5E%285%2F3%29%2BW%5E20%2BX%5E14%2BY%5E6+%3D+243157986743736595

but ... unfortunately wolframalpha seems stopping here to give back results.
Maybe too complex for the online solver.

[Charles Pegge]

You may be on the right track here Eros. After resolving the equations to a single unknown, say W. You will then end up with multiple powers of W each with a different coefficient. But this could be then solved by a few cycles of successive approximation.

Charles

[danbaron]

I don't have time now, guys, I have to catch a train.

But, I know that like everything else in math, mathematicians have studied methods to solve systems of nonlinear equations for many years.

I think that basically, many of the methods have to do with iteration.

I think the solution is considered as a vector.

In the case of the problem I made, it would be a vector with five components.

A trial vector is plugged into the equations, and then according to some error criterion, it is successively refined.

The main thing I was interested in, was showing that some problems are "one way".

If you start with the solution, you can easily construct the problem.

But, it is hard to start with the problem, and then find the solution.

I'll show how to make problems like this one, when I get home tonight.

(It is similar to cryptography, isn't it?)

Dan

[danbaron]

That's a nice picture zak. I don't know how you were able to get it so
perfectly.

If math will help you in some way, then you'll learn more, right Mike? In order
to learn something, you either have to want to, or need to, yes? In my
experience, almost no one will deeply study an area if he or she doesn't
anticipate some benefit. The benefit might be only emotional satisfaction.

If I understand you, Charles and Eros, then you are thinking about using
elimination, similar to for linear equations. I'm not an expert, but I don't
think you can. Say, I have the equations,

X^2 + Y^3 = 6

X^4 + Y^4 = 8.

I can multiply the first equation by X^2, and then I have,

X^4 + X^2*Y^3 = 6*X^2

X^4 + Y^4 = 8

Now, I can subtract the second equation from the first to get,

X^2*Y^3 - Y^4 = 6*X^2 - 8.

Now what?

--------------------------------------------------------------------------------

I'll show you what I did.

First, here is an analogy.

Imagine you are at the factory where they make safes (bank vaults). For each
safe, a combination is decided upon, and then the technician adjusts the safes's
mechanism for that combination. Say, for instance, the combination is, left 57,
right 09, left 93, right 34. The technician can easily set the combination. But,
if a person doesn't know that combination, then for him, opening the safe is
hard. If the number range is 0-99, then there are 100 million possible
combinations.

The math problem is similar to the safe.

The problem has 5 equations. Each equation has a left hand side (LHS), to the
left of the "=", and a right hand side (RHS), to the right of the "=".

Here is what I did.

1.
I invented the 5 LHSs.

2.
I chose integer values for the 5 variables, V, W, X, Y, Z.

3.
For each LHS, I substituted the values of V-Z, and calculated the result; call
it R.

4.
For each equation, I used its value of R, calculated from its LHS, for its RHS.
(So, the big numbers that are the RHSs, are the 5 values of R.)

The 5 RHSs, are the analogs of the safe's mechanism.

So, you can see that making the problem was easy, but maybe solving it is hard.
I think that is the general idea for modern cryptography, too.

We have mentioned using the "brute force" method, meaning trying different
integer combinations of V-Z, and hoping to eventually find the one combination that
makes all 5 equations correct. The trickier you are when you invent the LHSs and
choose the values of the variables, the harder you can make it for the brute
force method to succeed.

(Charles mentioned 4D graph paper, and Eros mentioned 5D TBGL. I might be wrong
about this, but just for fun ==> A sphere has 3 dimensions. A circle has two
dimensions. If a sphere has a radius of R, then how many circles of radius R
does it contain? The answer is infinity, right? Every plane that passes through
the sphere's center, intersects the sphere's surface to form a different circle
of radius R. Likewise, I think, a 4 dimensional sphere of radius R, contains an
infinity of 3 dimensional spheres of radius R. Imagine how much stuff you could
fit inside it!)

(I like the idea of Charles' Oxygen, but so far, I don't fully grasp what it is.
It's like if I saw something on the ground, and couldn't determine if it was
animal, vegetable, or mineral. Probably, I need the Baby's Guide to Oxygen, (and
the Baby's Reference Manual).)

Dan

[ErosOlmi]

Dan,

your way to explain things (here math) is very very fascinating.
You are able (at least in me) to create some kind of passion while I read.
The mix of real things (safes combinations, something you can touch and think to) and math method is a strong mix able to light many neurons in the brain of the reader.
Obviously you have strong teaching capabilities, passion and patience in writing that down. I appreciate it a lot.
I cannot image be in front of you listening to all such stuff, really.

That said ... I still do not have any solution :D

I can ask other forums I know to join this thread. Maybe someone has similar passions or just the fun of the challenge.

Eros

[Charles Pegge]

2 major tasks when applying the substitution method

1: Expansion of monstrous polynomials to extract all the terms of V..Z.

2: High precision maths beyond the normal limits - say double quad.

See what I mean:

rearrange equation 1 to get v

V^22=(002502992329277899-W^16 - X^12 - Y^08 - Z^03)

substitute v in equation 2

((002502992329277899-W^16 - X^12 - Y^08 - Z^03)^(1/22))^24 + W^20 + X^14 + Y^06 + Z^05 = 243157986743736595

to go further, the polynomial has to be expanded.

[ErosOlmi]

Solution:


--------------
v = 5
w = 7
x = 13
y = -53
z = 2511

Solved with:

Brute force (attached Power Basic PBCC5 source code + executable. Source is my original brute force modified with the below trick)
some time ... depending on the CPU you have
and ... a BIG clever analysis trick (merit is not mine, I will reveal it in a new post) that let you reduce the ranges of possible values of v, w, x, y, z


Updates:
_________________________________________________
version 2 of the Brute Force program: speed up operations breaking equation in multiple tokens calculated only when needed
version 3 of the Brute Force program: fixed a problem in calculating total number of iterations (zero is a valid option :oops: )

[kryton9]

You guys are something else, congratulations!

[ErosOlmi]

Here below the clever assumption made by the people to whom goes the merit of the solutions.
The below idea let the Brute Force program runs in a reasonable time window:


...
There is no need to search all possible values for v,w,x,y,z because with such large exponents the resulting values would be enormous.
So, on the assumption that this was done using standard PC maths, we can greatly narrow the likely ranges by inspection.

Compare the 3rd equation to the others.
V^25 out does all other terms and in no other equation does any term come close so it is likely that, for 18 digit maths, then V^25 < 1E19
i.e V can only reasonably be from -6 to +6.

Similarly for the other terms.
Only Z can have any significant variation because it's the only one with small exponents but even then, Zmax^5 needs to be less than 1E19 so Z must be between +/- 6300
...


Attached another Brute Force Power Basic program made by the above people that does the job in an even shorter time but because it does it trying to guess keys, you have to check manually if possible solutions is the right one comparing given results with original equations.

[ErosOlmi]

And the merit of the above solutions goes to ... (tada)

Paul Dixon from Power Basic forum where I posted this problem kindly offered by Dan Baron

http://www.powerbasic.com/support/pbforums/showthread.php?t=42906

_________________________________________________

Thanks to everybody ladies and gentlemen. See you at the next ... problem.

Good night
Eros

[ErosOlmi]

Updated my Brute Force version above.

Version 2 is 4x faster than previous attempt.
Version 2 speed up operations breaking equation in multiple tokens calculated only when needed

[danbaron]

I was writing this reply, and now I see that Eros solved it.

I looked at his source code, and he found the tricks.

We are limited to using QUADS (- 2^64/2 <= value <= + 2^64/2).

I think that, for instance, the Rijndael cryptographic algorithm uses 256 bit
keys. If we had an integer type in thinBasic such that [- 2^256/2 <= value <= +
2^256/2], then we could make the problem take 2^192 times as long to solve.

2^192 = 6.277 * 10^57.

I think that is the way cryptography now works. You make the number of
possibilities so big, that, statistically, the brute force method is very
unlikely to find the solution within a specified time period. Of course, as
computers become faster and faster, the number of possibilities must grow.
Maybe, in 10 years, keys will need to be 1024 bits (but probably not).

Now I am running Eros' program. I'll see how long it takes. He made it really
nice. Every one million iterations, it updates in the console window, the
elapsed time, the number of iterations completed, and the percent of the total
number of iterations completed. He was able to determine beforehand the lower
and upper bounds for each variable, otherwise, the total number of possible
iterations would have been infinity.

I'll write another post when Eros' program finishes.

He did a real good job. He is like a bulldog.

Below, is what I wrote concerning Charles' method.

Dan

---------------------------------

Let's look at my simpler example from before using Charles' method.

We have,

1. X^2 + Y^3 = 6

2. X^4 + Y^4 = 8.

---------------------------------

From Equation 1, we get

X^2 = 6 - Y^3.

---------------------------------

Therefore,

X^4 = (6 - Y^3)^2,

or,

X^4 = Y^6 - 12*Y^3 + 36.

---------------------------------

Substituting into Equation 2, we get,

Y^6 - 12*Y^3 + 36 + Y^4 = 8.

or,

Y^6 + Y^4 - 12*Y^3 + 28 = 0

That is a 6th degree polynomial, that can be numerically solved.

So, Charles's method seems to work in this case.

(However, an nth degree polynomial, has n roots (solutions), some of which are
real, and some of which are complex, depending on the coefficients. Here, the
coefficients are 1, 0, 1, -12, 0, 0, 28. I don't know how many of the roots are
real for this polynomial. Anyway, this is a complication to the method.)

---------------------------------

Now, let's change the original two equations, and try the method again.

1. X^2 + Y^3 = 6

2. X^3 + Y^4 = 8.

---------------------------------

Multiplying Equation 1 by X, we get

X^3 + X*Y^3 = 6*X.

Or,

X^3 = X*(6 - Y^3).

---------------------------------

Substituting into Equation 2, we get,

X*(6 - Y^3) + Y^4 = 8.

Or,

X = (8 - Y^4)/(6 - Y^3).

Therefore,

X^2 = ((8 - Y^4)/(6 - Y^3))^2.

---------------------------------

Substituting into Equation 1, we get,

((8 - Y^4)/(6 - Y^3))^2 + Y^3 - 6 = 0.

And, I think this equation can be solved numerically.
So, again, Charles' method seems to work in theory.

Let's try one more example.

---------------------------------

1. X*Y + X^2*Y^3 = 6

2. X^3*Y^2 + X^3*Y^4 = 8.

---------------------------------

From Equation 1,

X = (6 - X^2*Y^3)/Y.

Or,

Y = (6 - X^2*Y^3)/X.

Here, I think we are stuck.

I don't see any way to separate X from Y in this case.

---------------------------------

I think that Charles has found a way to numerically solve the problem, probably
not the easiest way, but a way.

It seems that if each factor (for instance, X^17) in the system of equations
contains only one variable, then Charles' method can work. But, if factors
contain multiple variables (for instance, X^3*Y^5*Z^7, or X^Y), then, I don't
think it will (but, I'm not Euler's descendant, I could be wrong).

[danbaron]

I can't keep up with these posts.

By the time I make one, two more have appeared.

Now, Eros has posted a faster version.

I am running the first version.

I will give the elapsed time for it, when it finishes.

Dan

[ErosOlmi]

Sorry Dan but there was an error in my program.

Uploaded version 3
Version 3 of the Brute Force program: fixed a problem in calculating total number of iterations (zero is a valid option :oops: )

On my computer (see my signature) it takes about 1600 seconds to find the solution.

[danbaron]

Now downloading new version.

Dan

[danbaron]

Now, it is confirmed for me.

The output is below.

All I can do is to learn from this attempt, and maybe try again.

Dan :unguee: :x :P

---------------------------------------------------------------------------
16,015,000,000 iterations out of 17,714,901,633 ( 090.4041% )
2147.48 seconds
---------------------------------------------------------------------------
Found: 5 7 13 -53 2511

[Charles Pegge]

---------------------------------

From Equation 1,

X = (6 - X^2*Y^3)/Y.

Or,

Y = (6 - X^2*Y^3)/X.

Here, I think we are stuck.

I don't see any way to separate X from Y in this case.


Yes Dan, It seems impossible to separate x and y in this apparently innocent equation.

However I found it helpful to rearrange the expression and once this was done, the solution required very little effort.

y=6/x - x^2*y^3/x

multiply thru by x:

x*y =6-x^2*y*3

change notation:

xy=6-xxyyy

null expression

6-xxyyy-xy

rearrange terms:

6-xyxyy-xy

then group them:

6 - xy.xy.y - xy



this suggests ther is a cube of 2 in there

and after playing with the signs
the solution is:
x=-1
y=-2

Charles

[danbaron]

Remember, Charles, the original equation was,

1. x*y + x^2*y^3 = 6.

--------------------------------------------------

If y = 0, then there is no solution for x, i.e., the curve never crosses the x
axis.

If x = 0, then there is no solution for y, i.e., the curve never crosses the y
axis.

--------------------------------------------------

If y = 1, then we get,

x^2 + x - 6 = 0.

Or,

(x + 3)*(x - 2) = 0.

Therefore, x = 2, or x = -3.

So we get the two points,

( 2, 1)
(-3, 1).

--------------------------------------------------

If y = 2, then we get,

8*x^2 + 2*x - 6 = 0.

Or,

(4*x - 3)*(2*x + 2) = 0.

Therefore, x = 3/4, or x = -1.

so we get the two points,

(3/4, 2)
( -1, 2).

--------------------------------------------------

If x = 0.001, then we (approximately) get, the point,

(0.001, 180).

If x = -0.001, then we (approximately) get, the point,

(-0.001, 184).

--------------------------------------------------

If x = 1000, then we (approximately) get, the point,

(1000, 0.0058 ).

If x = -1000, then we (approximately) get, the point,

(-1000, 0.03428 ).

--------------------------------------------------

Actually, it seems that the equation is of two curves, one confined to the first
quadrant, and the other confined to the second quadrant.

Anyway, there are an infinity of points which satisfy the equation.

Dan

[Charles Pegge]

Thanks Dan,

Yes I slipped up on the sign of 6.

I can see you could clamp x or y to any non-zero value and the equation would be satisfied by varying the other to come up with 6:

x*y+x*2y^3=6

y=1 : x=2
y=2 : 2x+8x^2=6
y=3 : 3x+27x^2=6
y=4 : 4x+64x^2=6
y=5 : 5x+125x^2=6
etc.

So this expression describes curved lines not a single point. The lines have a boundary at x=0 and/or y=0 but no ends.

Charles

[danbaron]

Now we agree, Charles.

Dan

[ErosOlmi]

In PowerBasic forum user Rodney Hicks gave some possible alternative direction to Problem 1.
Worth a check:

http://www.powerbasic.com/support/pbforums/showpost.php?p=337134&postcount=9

[danbaron]

I've been thinking about the same general thing, how to actually solve one of these problems, not just to try every possible solution.

I'm not optimistic.

[kryton9]

Computers are cheap now a days. Why not just assign a computer for just one equation and use brute force. Then look for matches in the solutions, as you see 2 or more equations lets say using the same value for a variable, then alter the others to use those variable to even brute force faster.
I am a few computers short for the task, but it would be neat to see how fast it could be done this way.

[danbaron]

You can't assign one computer for one equation.
There are five variables, so there must be five equations.
Each of the five equations contains each of the five variables.
All five equations must be true for all of the same five variables.
If there are five variables, and less than five equations, then the system is under constrained.
Say, I have the two equations,

x + y = 13
2x + 3y = 33.

I can't just solve,

x + y = 13,

by itself.

It is under constrained.
There are two variables, but only one equation.
Therefore, there are an infinity of points that can make the equation true.

If x = 1, then y = 12.
If x = 2, then y = 11.
If x = 123456, then y = -123443.

Both equations must be solved at once.
In that case, there is only one solution,

x = 6, y = 7.

Problem 1 was solved by brute force. If I remember correctly, it had approximately 2*10^10 possible solutions.

Problem 2 is a lot worse. It has six variables, six equations, and smaller exponents. There are more than 2*10^48 possible solutions, and only one of them is correct.

Each trial solution must contain candidate values for all six of the variables.

Say, you had one quintillion (1 billion * 1 billion) computers, each trying one quintillion solutions of the six equations per second.
And say, that the computers were synchronized so that none of them duplicated trial solutions.

Then, it would take them 63,376 years to try every solution for Problem 2.

No matter how fast computers become, and no matter how many you have working together, it will always be easy to construct problems that they cannot be reliably depended on to solve by brute force.

Statistically, the probability that a problem will be solved within any reasonable time period by brute force, becomes tiny. On the other hand, the probability is always greater than 0, that one computer could solve it on the first guess. Similarly, the probability is greater than 0, that all of the air molecules in the room in which I am sitting, will suddenly move to the other half of the room, and I will suffocate (it is true, that probability is greater than 0, the calculation can be done).

Now, in strong cryptography 256 bit keys are used. So there are 2^256 possible keys, and only one is correct. 2^256 is approximately equal to 10^77. So, by brute force, it is virtually impossible to decode a file. You need to know the algorithm used for encoding, and try to find some extra information there.

Similarly, for Problem 2. Brute force is a dead end. But there are numerical methods for solving systems of nonlinear equations. Most likely, one of them would work, maybe in a matter of minutes.

Dan :twisted:

[REDEBOLT]

i ran the program by Eros in post #18 and got the following results:


Project Lovecraft Problem 1
------------------------------------------------------------------
16015000000 iterations out of 17714901633 ( 090.4041% )
1814.95 seconds
------------------------------------------------------------------
Found: 5 7 13 -53 2511

[danbaron]

Good, REDEBOLT, because, those are the correct answers.

So, I'm glad they are what you got.

:bom:

Dan