Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

answered 4 years ago

Max Alekseyev gravatar image

The question amount to substituting given x in the elliptic curve equation, and solving the resulting quadratic equation for y. Here is a sample code:

def compute_y(E,x):
    R = E.base_ring()
    x = R(x)
    a = E.a_invariants()
    c = (a[0]*x + a[2])/2
    b = x^3 + a[1]*x^2 + a[3]*x + a[4] + c^2
    if not is_square(b):
        return None
    return sqrt(b)-c

E = EllipticCurve(GF(43),[2,8]);
print( compute_y(E,1) )

For a given curve and x=1, it computes y=21. It is easy to verify that 212=13+21+8 in GF(43).

click to hide/show revision 2
No.2 Revision

The question amount to substituting given x in the elliptic curve equation, and solving the resulting quadratic equation for y. Here is a sample code:

def compute_y(E,x):
    R = E.base_ring()
    x = R(x)
    a = E.a_invariants()
    c = (a[0]*x + a[2])/2
    b = x^3 + a[1]*x^2 + a[3]*x + a[4] + c^2
    r = is_square(b,True)
    if not is_square(b):
r[0]:
        return r[1]-c
    else:
        return None
    return sqrt(b)-c

E = EllipticCurve(GF(43),[2,8]);
print( compute_y(E,1) )

For a given curve and x=1, it computes y=21. It is easy to verify that 212=13+21+8 in GF(43).

click to hide/show revision 3
No.3 Revision

The question amount to substituting given x in the elliptic curve equation, and solving the resulting quadratic equation for y. Here is a sample code:

def compute_y(E,x):
    R = E.base_ring()
    x = R(x)
    a = E.a_invariants()
    c = (a[0]*x + a[2])/2
    b = x^3 + a[1]*x^2 + a[3]*x + a[4] + c^2
    r = is_square(b,True)
    if r[0]:
        return r[1]-c
    else:
        return None

E = EllipticCurve(GF(43),[2,8]);
EllipticCurve(GF(43),[2,8])
print( compute_y(E,1) )

For a given curve and x=1, it computes y=21. It is easy to verify that 212=13+21+8 in GF(43).

click to hide/show revision 4
No.4 Revision

The question amount amounts to substituting given x in the elliptic curve equation, and solving the resulting quadratic equation for y. Here is a sample code:

def compute_y(E,x):
    R = E.base_ring()
    x = R(x)
    a = E.a_invariants()
    c = (a[0]*x + a[2])/2
    b = x^3 + a[1]*x^2 + a[3]*x + a[4] + c^2
    r = is_square(b,True)
    if r[0]:
        return r[1]-c
    else:
        return None

E = EllipticCurve(GF(43),[2,8])
print( compute_y(E,1) )

For a given curve and x=1, it computes y=21. It is easy to verify that 212=13+21+8 in GF(43).

click to hide/show revision 5
No.5 Revision

The question amounts to substituting given x in the elliptic curve equation, and solving the resulting quadratic equation for y. Here is a sample code:

def compute_y(E,x):
    R = E.base_ring()
    x = R(x)
    a = E.a_invariants()
    c = (a[0]*x + a[2])/2
    b = x^3 + a[1]*x^2 + a[3]*x + a[4] + c^2
    r = is_square(b,True)
    if r[0]:
        return r[1]-c
    else:
        return None

E = EllipticCurve(GF(43),[2,8])
print( compute_y(E,1) )

For a given curve and x=1, it computes y=21. It is easy to verify that 212=13+21+8 in GF(43).

P.S. The code above does not work if 2 is not invertible in the in the base ring (e.g., if it's a filed of characteristic 2) since it involves division by 2. Although, when a[0]=a[2]=0, we can avoid division and simply set c=0.

click to hide/show revision 6
No.6 Revision

The question amounts to substituting given x in the elliptic curve equation, and solving the resulting quadratic equation for y. Here is a sample code:

def compute_y(E,x):
    R = E.base_ring()
    x = R(x)
    a = E.a_invariants()
    c = (a[0]*x + a[2])/2
    b = x^3 + a[1]*x^2 + a[3]*x + a[4] + c^2
    r = is_square(b,True)
    if r[0]:
        return r[1]-c
    else:
        return None

E = EllipticCurve(GF(43),[2,8])
print( compute_y(E,1) )

For a given curve and x=1, it computes y=21. It is easy to verify that 212=13+21+8 in GF(43).

P.S. The code above does not work if 2 is not invertible in the in the base ring (e.g., if it's a filed of characteristic 2) since it involves division by 2. Although, when a[0]=a[2]=0, we can avoid division and simply set c=0.

click to hide/show revision 7
No.7 Revision

The question amounts to substituting given x in the elliptic curve equation, and solving the resulting quadratic equation for y. Here is a sample code:

def compute_y(E,x):
    R = E.base_ring()
    x = R(x)
    a = E.a_invariants()
    c = (a[0]*x + a[2])/2
    b = x^3 + a[1]*x^2 + a[3]*x + a[4] + c^2
    r = is_square(b,True)
    if r[0]:
        return r[1]-c
    else:
        return None

E = EllipticCurve(GF(43),[2,8])
print( compute_y(E,1) )

For a given curve and x=1, it computes y=21. It is easy to verify that 212=13+21+8 in GF(43).

P.S. The code above does not work if 2 is not invertible in the base ring (e.g., if it's a filed field of characteristic 2) since it involves division by 2. Although, when a[0]=a[2]=0, we can avoid division and simply set c=0.

click to hide/show revision 8
No.8 Revision

The question amounts to substituting given x in the elliptic curve equation, and solving the resulting quadratic equation for y. Here is a sample code:

def compute_y(E,x):
    R R.<y> = E.base_ring()
    x = R(x)
PolynomialRing(E.base_ring())
    a = E.a_invariants()
    c L = (y^2 + (a[0]*x + a[2])/2
    b = x^3 a[2])*y - (x^3 + a[1]*x^2 + a[3]*x + a[4] + c^2
    r = is_square(b,True)
    if r[0]:
    a[4])).roots()
    return r[1]-c
    else:
        return None
{l[0] for l in L}

E = EllipticCurve(GF(43),[2,8])
print( compute_y(E,1) )

For a given curve and x=1, it computes y=21. that y{21,22}. It is easy to verify that $21^2 = 22^2 = 1^3 + 2\cdot 1 + 8$ and in GF(43).

P.S. The code above does not work if 2 is not invertible in the base ring (e.g., if it's a field of characteristic 2) since it involves division by 2. Although, when a[0]=a[2]=0, we can avoid division and simply set c=0.