need formula for mathematical problem either mathematically or using an algorithm

[anonymousking123]

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.

[Phi for All]

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

[anonymousking123]

 

!

Moderator Note

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

so do you have any idea how to solve this issue?

[anonymousking123]

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.

[fiveworlds]

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 February 7, 2015 by fiveworlds

[anonymousking123]

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 = b^2x

for x.

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

q = b^x

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 = b^2x

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

log_b(q) = 2^x mod N

Edited February 7, 2015 by anonymousking123

[Strange]

thats wrong it is not correct

 

You will soon learn to ignore 99% of fiveworld's posts.

[imatfaal]

!

Moderator Note

 

anonymousking123

 

please don't swear or use foul language - even in frustration

 

[John]

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 (x² - 1)² = 6400, which means the formula will never reach 10 for any p where 6400 = 0 (mod p), or for which (6400² - 1)² = 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 February 7, 2015 by John

[anonymousking123]

The 'p' in (mod p) is 2^255 - 19 and I'm not searching for 10 but rather some arbitrarily large number such as83402281777707715381485212681368749158073214888176003645002923212220704930559

Edited February 7, 2015 by anonymousking123

[John]

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?

[anonymousking123]

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 February 8, 2015 by anonymousking123

[anonymousking123]

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.

[anonymousking123]

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.