Revision history [back]

The following answer does not implement the two functions "add" and "double" on an elliptic curve, instead, it uses the already existing functionality of sage. (It would be too much to implement also these basic functions depending on the form of the elliptic curve and the base field characteristic.)

Code:

def left_to_right_double_and_add(n, G):
    """n is a positive integer number,
    G is a rational point of an elliptic curve E, 
    defined over some finite field F.
    This routine computes
    n*G
    in an ad-hoc manner.
    We use the standard add, and doubling on E,
    and do not implemented them here.
    """
    digits = ZZ(n).digits(base=2)
    E = G.curve()
    # F = E.base_field()
    P = G    # this corresponds to 1*G, init
    nG = E(0)    # and we add further contributions
    for digit in digits:
        if digit:
            nG = nG.__add__(P)    # or simply nG += P
        P = P.__mul__(2)          # or simply P  *= 2
        # print "\tdigit=%s P=%s nG=%s" % (digit, P, nG)
    return nG

# quick test on the given curve with the given poing:
E = EllipticCurve( GF(37), [7, 25] )
G = E.point( [33, 9] )

for n in [1..9]:
    nG = left_to_right_double_and_add(n, G)
    print ( "sage %s*G = %13s | ad-hoc %s*G = %13s | Are they equal? %s"
            % ( n, n*G, n, nG, n*G == nG ) )

This gives in the test:

sage 1*G =  (33 : 9 : 1) | ad-hoc 1*G =  (33 : 9 : 1) | Are they equal? True
sage 2*G =  (9 : 15 : 1) | ad-hoc 2*G =  (9 : 15 : 1) | Are they equal? True
sage 3*G =  (2 : 11 : 1) | ad-hoc 3*G =  (2 : 11 : 1) | Are they equal? True
sage 4*G = (35 : 15 : 1) | ad-hoc 4*G = (35 : 15 : 1) | Are they equal? True
sage 5*G =  (15 : 8 : 1) | ad-hoc 5*G =  (15 : 8 : 1) | Are they equal? True
sage 6*G = (30 : 22 : 1) | ad-hoc 6*G = (30 : 22 : 1) | Are they equal? True
sage 7*G =  (1 : 25 : 1) | ad-hoc 7*G =  (1 : 25 : 1) | Are they equal? True
sage 8*G = (31 : 27 : 1) | ad-hoc 8*G = (31 : 27 : 1) | Are they equal? True
sage 9*G = (17 : 32 : 1) | ad-hoc 9*G = (17 : 32 : 1) | Are they equal? True