Topic: how to get X value from Y (Read 1437 times)
Very enlighting Andyoshi.
Thank you andytoshi, development purpose I ask this question
Hi sss555,
If you can, installing sage and using that rather than Python will make your life much easier. There is an example notebook on bitcoin.ninja which does some ECDSA stuff on Bitcoin's curve.
To directly answer your question, we can get x from y in basically the same way you got y from x. To see this, let's walk through why your method works.
We have from our curve equation that Y = y^2 = x^3 + 7. You can compute Y easily from x, then you're solving Y = y^2 for y. By Fermat's Little Theorem we can write 1 = y^(p - 1) = Y^(p - 1)/2. Write Q = (p - 1)/2; then we have Y^Q = 1, so Y^(Q + 1) = Y = y^2, so Y^((Q + 1)/2) = y. As it turns out, (Q + 1)/2 = (p + 1)/4, which is why you were able to solve for y by using an exponent of (p + 1)/4. Notice that this depends crucially on p being 3 mod 4; otherwise (p + 1)/4 would not be an integer and we wouldn't be able to compute this. Fortunately our choice of p satisfies this.
OK! So let's do the analogous thing for x. Let's write X = x^3 = y^2 - 7. X can be computed from y easily, so we need to solve X = x^3. Write Q = (p - 1)/3; then X^Q = x^(p - 1) = 1, so X^(Q + 1) = Q = x^3, so X^((Q + 1)/3) = x. As it turns out, (Q + 1)/3 = (p + 2)/9. This time we depend crucially on p being 7 mod 9, in order that this is an integer. Luckily it is! So there you go.
TL;DR use (p + 2)/9 in place of (p + 1)/4.
Edit: Oh, and to get the other two cube roots you multiply by a nontrivial cube root of 1. (Similar to you multiplying by -1 in your original code.) One such cube root is 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee.
Edit2: Here is Python code analogous to yours. It takes one of your output y values and returns the input x value as x2.
Its output is
If you can, installing sage and using that rather than Python will make your life much easier. There is an example notebook on bitcoin.ninja which does some ECDSA stuff on Bitcoin's curve.
To directly answer your question, we can get x from y in basically the same way you got y from x. To see this, let's walk through why your method works.
We have from our curve equation that Y = y^2 = x^3 + 7. You can compute Y easily from x, then you're solving Y = y^2 for y. By Fermat's Little Theorem we can write 1 = y^(p - 1) = Y^(p - 1)/2. Write Q = (p - 1)/2; then we have Y^Q = 1, so Y^(Q + 1) = Y = y^2, so Y^((Q + 1)/2) = y. As it turns out, (Q + 1)/2 = (p + 1)/4, which is why you were able to solve for y by using an exponent of (p + 1)/4. Notice that this depends crucially on p being 3 mod 4; otherwise (p + 1)/4 would not be an integer and we wouldn't be able to compute this. Fortunately our choice of p satisfies this.
OK! So let's do the analogous thing for x. Let's write X = x^3 = y^2 - 7. X can be computed from y easily, so we need to solve X = x^3. Write Q = (p - 1)/3; then X^Q = x^(p - 1) = 1, so X^(Q + 1) = Q = x^3, so X^((Q + 1)/3) = x. As it turns out, (Q + 1)/3 = (p + 2)/9. This time we depend crucially on p being 7 mod 9, in order that this is an integer. Luckily it is! So there you go.
TL;DR use (p + 2)/9 in place of (p + 1)/4.
Edit: Oh, and to get the other two cube roots you multiply by a nontrivial cube root of 1. (Similar to you multiplying by -1 in your original code.) One such cube root is 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee.
Edit2: Here is Python code analogous to yours. It takes one of your output y values and returns the input x value as x2.
Code:
## Input
y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
## Field parameters
# Field modulus
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
# Cube root of 1
beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee
## Actual code
xcubed = (y*y - 7) % p
print "xcubed = 0x%x" % xcubed
x = pow(xcubed, (p + 2) / 9, p)
print "x1 = 0x%x" % x
print "x2 = 0x%x" % (x * beta % p)
print "x3 = 0x%x" % (x * beta * beta % p)
Code:
xcubed = 0x4866d6a5ab41ab2c6bcc57ccd3735da5f16f80a548e5e20a44e4e9b8118c26eb
x1 = 0xc994b69768832bcbff5e9ab39ae8d1d3763bbf1e531bed98fe51de5ee84f50fb
x2 = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
x3 = 0xbcace2e99da01887ab0102b696902325872844067f15e98da7bba04400b88fcb
http://bitcoin.stackexchange.com/questions/38740/bitcoin-how-to-get-x-value-from-y
How to get X value from Y?
here getting y value from x
X = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Python code,
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
ysquared = ((x*x*x+7) % p)
print "ysquared= %s " % hex(ysquared)
y = pow(ysquared, (p+1)/4, p)
print "y1 = %s " % hex(y)
print "y2 = %s " % hex(y * -1 % p)
Output
Y1 = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
Y2 = 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777
print hex((x**3 + 7 - y1**2) % p) // output 0
print hex((x**3 + 7 - y2**2) % p) // output 0
above python code to get Two possible y values from x
like the same how to get possible x values from y?,
Is it any formula or script available
My question is how to get x value from y
How to get X value from Y?
here getting y value from x
X = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Python code,
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
ysquared = ((x*x*x+7) % p)
print "ysquared= %s " % hex(ysquared)
y = pow(ysquared, (p+1)/4, p)
print "y1 = %s " % hex(y)
print "y2 = %s " % hex(y * -1 % p)
Output
Y1 = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
Y2 = 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777
print hex((x**3 + 7 - y1**2) % p) // output 0
print hex((x**3 + 7 - y2**2) % p) // output 0
above python code to get Two possible y values from x
like the same how to get possible x values from y?,
Is it any formula or script available
My question is how to get x value from y
Jump to: