In [6]:
prime = 1035418103
var_a = 45181635
var_b = 124806060

E = EllipticCurve(GF(prime), [1, 0, 0, var_a,var_b])

P = E.gen(0);
print('P: %s, n: %d' %(P, P.order()))

P: (299835419 : 368012477 : 1), n: 1035437671
In [7]:
import time

current_milli_time = lambda: int(round(time.time() * 1000))

REPEATED DOUBLE AND ADD METHOD

This method is used to compute $Q = lP$ for for a given generator $P$ and scalar multiplier $l$

In [8]:
def compute_lP(l, P):
    l_binary = bin(l)[2:]
    i_initial = l_binary[-1]

    A = P

    if i_initial == '0':
        B = P.order() * P
    else:
        B = P
    for i in reversed(l_binary[:-1]):
        A = A + A
        if i == '1':
            B = B + A
    return B

SHANK'S ALGORITHM

Shank's algorithm solves the ECDLP considerably faster than brute force. However, its running time is still fully exponential. Shank's algorithm has running time $O(\sqrt{m} = O(\sqrt{n}) = O(\sqrt{p})$ point additions. It also requires $O(\sqrt{p})$ storage.

Computes scalar multiplier $l$ for a given $P$ and $Q$, where $Q = lP$

In [15]:
import math
import random

def shanks_algorithm(P, Q):
    m = int(math.ceil(math.sqrt(prime)))
    q, r = divmod(l, m)
    
    points = dict()

    for r in range(m):
        if r == 0:
            R = r*P
        else:
            R += P
        points[R] = r
    M = compute_lP(m, P)
    print('# of points stored: %d, m: %d' %(len(points), m))
    
    for q in range(m):
        R = Q - q*M
        if R in points:
            r = points[R]
            computed_l = q*m + r
            return computed_l


l = random.randint(0, prime)
l = 884158742
Q = compute_lP(l, P)

start_timestamp = current_milli_time()
computed_l = shanks_algorithm(P, Q)
end_timestamp = current_milli_time()
print('Time elapsed', end_timestamp - start_timestamp)
print('Solution: %s, Q: %s, successful? %s' %(computed_l, Q, Q == computed_l * P))

# of points stored: 32178, m: 32178
('Time elapsed', 13398)
Solution: 884158742, Q: (830731058 : 402455075 : 1), successful? True
In [ ]: