Jump to content

need formula for mathematical problem either mathematically or using an algorithm


anonymousking123

Recommended Posts

Problem Description:

Being a some constant, further assume that we
are in a factor ring (basically all operations modulo some sumber p). Note, that the division below is a multiplication by the modular inverse.
You always have to start with x=9.
Consider the following recursive formula:

Code:
new_x = (x²-1)² / (4*x*(x²+a*x+1))

How often do you have to perform this operation to get a specific x (basically getting the new_x and feeding it back into the formula to get another new_x, and so on)?
Note: You can start multiple such chains beginning at x=9, and add the resulting x values
using the addition algorithm from http://en.wikipedia.org/wiki/Montgomery_curve (Montgomery arithmetic section).
Note, that the x value, is the value you get at the end of such calculation-chain, and the z value is always 1.

The answer:
The formula must work in all cases, and be computationally feasible (let us say calculable in less than 24 hours).

 

 

NOTES:

 

For the record, this is the posted solution:

Code:
<script>
var equation= "(x²-1)² / (4*x*(x²+a*x+1))";
var a=0;
var b=10;
while(a<b)
{
var equation = equation.replace("x", "(x²-1)² / (4*x*(x²+a*x+1))");
a=a+1;
}
document.write(equation);
</script>
Where b is the specific new_x you are looking for so for new_x=10

(((((((((((x²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))²-1)² / (4*x*(x²+a*x+1))
where x=9

By no means the formula evaluates to 10, when I insert 9.
Also, additionally to that, the division must be a multiplication with the modular inverse modulo p (just as a hint for future tries).

 

 


@MODS: Also, this has nothing to do with homework, this to solve a complex problem with some suspect code ive been writing and i need a science formula or math formula expert and it needs to be correct


*-ring[edit]
In mathematics, a *-ring is a ring with a map * : A → A that is an antiautomorphism and an involution.

More precisely, * is required to satisfy the following properties:[1]

(x + y)* = x* + y*
(x y)* = y* x*
1* = 1
(x*)* = x
for all x, y in A.

Link to comment
Share on other sites

@MODS: Also, this has nothing to do with homework, this to solve a complex problem with some suspect code ive been writing and i need a science formula or math formula expert and it needs to be correct

 

!

Moderator Note

OK, not homework, and a public posting of answers. We're good. :)

Link to comment
Share on other sites

  • 2 weeks later...

could be easily done, by actually using the x-coordinate only. Right now the Montgomery Curve 25519 is transformed to Kolbitz Representation with full (x,y) instead of only the (x) coordinate. Also, addition is not made using montgomery-steps but by simple mathematic arithmetic. Should be doable.

Link to comment
Share on other sites

here

var equation = equation.replace("x", "(x²-1)² / (4*x*(x²+a*x+1))");

should read

var equation = equation.replace(/x/gi, "(x²-1)² / (4*x*(x²+a*x+1))");

which I already tested for you

<script>
var equation= "(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))";
var a=0;var b=1;var x=9;

document.write(equation+"</br>");
while(a<b)
{
var equation = equation.replace(/x/gi, "(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))");

document.write(equation+"</br>");
a=a+1;
}
var x2=x*x;


var answer=(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1));

document.write(answer+"</br>");
var answer=((x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*x-1)*(x*x-1) / (4*x*(x*x+a*x+1));
document.write(answer+"</br>");

var x=9;

var answer=(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1));
document.write(answer+"</br>");
var x=answer;
var answer=(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1));
document.write(answer+"</br>");



var x=9;
var answer=((x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))-1)*((x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))-1) / (4*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*((x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))+a*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))+1))
document.write(answer+"</br>");
</script>

I also changed (x²-1)² / (4*x*(x²+a*x+1)) and used (x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1)) instead because javascript can directly evaluate it. Just for demonstation purposes I left

var x=9;

var answer=(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1));
document.write(answer+"</br>");
var x=answer;
var answer=(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1));
document.write(answer+"</br>");

which is evaluation by recursion. Find the answer plug it back into the equation etc. Compared with the created equation

var x=9;
var answer=((x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))-1)*((x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))-1) / (4*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*((x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))+a*(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))+1))
document.write(answer+"</br>");

both of which return the same answer so the code in the end is

<script>
var equation= "(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))";var a=0;var b=6;var x=9;var c=0;document.write(eval(equation)+"</br>");
while(c<b){var equation = equation.replace(/x/gi, "(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))");
document.write(equation+"</br></br>");document.write(eval(equation)+"</br>");c=c+1;}
</script>

This will give you just the answers minus the equations

<script>
var equation= "(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))";var a=0;var b=6;var x=9;var c=0;document.write(eval(equation)+"</br>");
while(c<b){var equation = equation.replace(/x/gi, "(x*x-1)*(x*x-1) / (4*x*(x*x+a*x+1))");
document.write(eval(equation)+"</br>");c=c+1;}
</script>
Edited by fiveworlds
Link to comment
Share on other sites

thats wrong it is not correct


If you have a generator element b of an additive group of order N, and you know it takes x repeated doubling operations (squaring operations in the context of a multiplicative group) on this element in order to reach q then you have effectively solved [multiplicative group notation]:

q = b2x

for x.

What we really want to do is crack the discrete logarithm, which means finding x in the context of:

q = bx

So the question becomes: if we can solve the first equation can we solve the second? The answer is yes. The reason is that the exponent of b is itself an element of it's own multiplicative group ℤN× of which 2 is a generator since N is prime (at least in the context of Curve25519 or secp256k1).

So if you find x that satisfies:

q = b2x

then you can use your solution to solve the discrete log easy peasy lemon squeezy.:

logb(q) = 2x mod N

Edited by anonymousking123
Link to comment
Share on other sites

I'm not entirely sure what you're asking here, but a couple of things popped into my mind while reading:

1. Using the formula for new_x presented in your OP, if we have to start with x = 9, then we have (x2 - 1)2 = 6400, which means the formula will never reach 10 for any p where 6400 = 0 (mod p), or for which (64002 - 1)2 = 1677721518080001 = 0 (mod p), etc.

 

2. Though you possibly qualified it by saying "at least in the context of...", I just thought I'd note that 2 is not necessarily a generator of ℤp× where p is prime. Consider, for example, p = 7.

Of course, I may be misunderstanding entirely what you're wanting to do.

Edited by John
Link to comment
Share on other sites

Alright, though you did say any formula we produce should work "in all cases," which I take to mean for general p and general x.

 

Having re-read the thread, I noticed a few things I missed earlier. Are you essentially trying to find a general method for quickly finding the discrete logarithm? Are you looking to break elliptic curve cryptography?

Link to comment
Share on other sites

pm sent so take that as a yes and as far as anyone else can make out of this, were looking to prevent this vulnerability we found somewhere from happening so anyone with any advice would and could be potentially rewarded if they'd like as a prize!

Edited by anonymousking123
Link to comment
Share on other sites

Well, this is the point,
let us say you have the following parameters:

a = 486662
modulus = 2^255 - 19

Then you are right, to look for new_x=10 cannot be obtained by the formula, that means there is no "point doubling possible" that will result in new_x = 10 from any starting point.



But you can use montgomery point addition to add x=9 to the desired new_10 = 10, but this point can be maybe obtained by looking for different points than newx_10, which then (added by montgomery rules) will result in new_x = 10.
This is the essential task here.

Link to comment
Share on other sites

An approach idea.

Take an arbitrary x value (the one that is looked for, and find the point, that caused that value when inserted into the formula.
In Mathematica that would be:

Solve[(x*x - 1)^2/(4*x*(x*x + 486662*x + 1)) == THEVALUETOLOOKFOR, Modulus -> 2^255 - 19]

Then go back the whole chain, unti you reach x=9.
This can sometimes be tricky, that is why you probably have to think about it further.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.