1709.sagews

def add_points_on_elliptic_curve(K, A, P_1, P_2):
    x_1 = K(P_1[0])
    y_1 = K(P_1[1])
    
    if len(P_1) > 2:
        z_1 = K(P_1[2])
    else:
        z_1 = K(1)

    x_2 = K(P_2[0])
    y_2 = K(P_2[1])
    
    if len(P_2) > 2:
        z_2 = K(P_2[2])
    else:
        z_2 = K(1)
    
    if z_1 == 0:
        return P_2
    
    if z_2 == 0:
        return P_1
        
    if x_1 == x_2 and y_1 == K(-y_2):
        return (0, 1, 0)
        
    if x_1 == x_2 and y_1 == y_2:
        slope = K(3*x_1^2 + A) * K(2*y_1)^(-1)
    else:
        slope = K(y_1 - y_2) * K(x_1 - x_2)^(-1)
            
    x_3 = K(slope ^2 - x_1 - x_2)
    y_3 = K(-slope*x_3 - (y_1 - slope*x_1))
    P_3 = (x_3, y_3)

    return P_3

def check_identity(K, A, L):
    for P_1 in L:
        for P_2 in L:
            a = add_points_on_elliptic_curve(K, A, P_1, P_2)
            b = add_points_on_elliptic_curve(K, A, P_2, P_1)

            if a == P_1 and b == P_1:
                print "The identity of this set is ",P_2
                return
                
            if a == P_2 and b == P_2:
                print "The identity of this set is ",P_1
                return

    print "The set does not have an identity element."

def check_closure(K, A, L):
    for P_1 in L:
        for P_2 in L:
            P_3 = add_points_on_elliptic_curve(K, A, P_1, P_2)
                    
            if not P_3 in L:
                print "This set is not closed under addition."
                print "%s + %s = %s"%(P_1, P_2, P_3)
                return
    print "The set is closed under addition." 

def check_inverses(K, A, L):
    for P_1 in L:
        found_inverse = false
        
        for P_2 in L:
            a = add_points_on_elliptic_curve(K, A, P_1, P_2)
            b = add_points_on_elliptic_curve(K, A, P_2, P_1)
                    
            if a == (0, 1, 0) and b == (0, 1, 0):
                found_inverse = true
                break


        if found_inverse == false:
            print "%s does not have an additive inverse in this set."%P_1
    print "Every element in this set has an inverse."

def check_associativity(K, A, L):
    for a in L:
        for b in L:
            for c in L:
                d = add_points_on_elliptic_curve(K, A, add_points_on_elliptic_curve(K, A, a, b), c)
                e = add_points_on_elliptic_curve(K, A, a, add_points_on_elliptic_curve(K, A, b, c))
            
                if d != e:
                    print "The set is not associative under addition."
                    print "(%s + %s) + %s = %s != %s = %s + (%s + %s)"%(a, b, c, d, e, a, b, c)
                    return
    print "This set is associative under addition."

#E = EllipticCurve(GF(7), [-3,2])

# Problem #1

K = GF(7)
L = [(0, 1, 0)]
for x in K:
    for y in K:
        if y^2 == x^3 + -3*x + 2:
            L.append((x, y))


print "The set is %s"%L


check_identity(K, -3, L)
check_closure(K, -3, L)
check_inverses(K, -3, L)
check_associativity(K, -3, L)

The set is [(0, 1, 0), (0, 3), (0, 4), (1, 0), (2, 2), (2, 5), (5, 0), (6, 2), (6, 5)] The identity of this set is (0, 1, 0) The set is closed under addition. Every element in this set has an inverse. The set is not associative under addition. ((0, 3) + (1, 0)) + (1, 0) = (0, 1, 0) != (0, 3) = (0, 3) + ((1, 0) + (1, 0))

# Problem 2

E = EllipticCurve(QQ, [1, -11])
print E

y(x) = 27/8 * x - 49/8
p = expand(x^3 - 11 - y^2)
print p
for root in p.roots():
    a = root[0]
    b = sqrt(a^3 - 11)
    if b^2 == a^3 - 11:
        print (a, b)

Elliptic Curve defined by y^2 = x^3 + x - 11 over Rational Field x |--> x^3 - 729/64*x^2 + 1323/32*x - 3105/64 (345/64, 6179/512) (3, 4)

K = GF(7)
E = EllipticCurve(K, [1,0])
print E
print ""
L = []
for (x, y, z) in E:
    if z == 0:
        L.append((x, y, z))
    else:
        L.append((x, y))

print "The elements of %s\nare %s"%(E,L)
print ""

check_identity(K, 1, L)
check_closure(K, 1, L)
check_inverses(K, 1, L)
check_associativity(K, 1, L)

for P in L:
    a = (0, 1, 0)
    generated_elements = [(0, 1, 0)]
    while True:
        a = add_points_on_elliptic_curve(K, 1, a, P)
        generated_elements.append(a)
        if a == (0, 1, 0) and len(generated_elements) > 2:
            break
    if set(L) == set(generated_elements):
        print "This set is cyclic and generated by ",P
        print generated_elements

Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7 The elements of Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7 are [(0, 0), (0, 1, 0), (1, 3), (1, 4), (3, 3), (3, 4), (5, 2), (5, 5)] The identity of this set is (0, 1, 0) The set is closed under addition. Every element in this set has an inverse. This set is associative under addition. This set is cyclic and generated by (3, 3) [(0, 1, 0), (3, 3), (1, 4), (5, 5), (0, 0), (5, 2), (1, 3), (3, 4), (0, 1, 0)] This set is cyclic and generated by (3, 4) [(0, 1, 0), (3, 4), (1, 3), (5, 2), (0, 0), (5, 5), (1, 4), (3, 3), (0, 1, 0)] This set is cyclic and generated by (5, 2) [(0, 1, 0), (5, 2), (1, 4), (3, 4), (0, 0), (3, 3), (1, 3), (5, 5), (0, 1, 0)] This set is cyclic and generated by (5, 5) [(0, 1, 0), (5, 5), (1, 3), (3, 3), (0, 0), (3, 4), (1, 4), (5, 2), (0, 1, 0)]