In [10]:
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 [11]:
import time

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

POLLARD'S LAMBDA ALGORITHM (CATCHING KANGAROOS METHOD)

In [13]:
import hashlib
import numpy as np
import math
import random
import struct


def hash_function(point):
    bytes = struct.pack('f'*len(point), *point)
    return hashlib.md5(bytes).hexdigest()


def get_next_x_and_jump_size(P, x, d):
    hexdigest = hash_function(x)
    as_int = int(hexdigest, 16)
    power_of_two = int(math.pow(2, (as_int % d) + 1))
    return x + power_of_two*P, power_of_two


def get_of_powers_of_two(limit):
    powers_of_two = set()
    for i in range(limit+1):
        powers_of_two.add(int(math.pow(2, i)))
    return list(powers_of_two)


def catch_kangaroos():
    a = 0
    b = int(0.39*prime)
    square_root_of_range = math.sqrt(b-a)
    d = int(math.log(square_root_of_range, 2) + math.log(math.log(square_root_of_range, 2), 2) - 2)

    powers_of_two = get_of_powers_of_two(d)
    beta = 1.39
    alpha = math.sqrt(b * (1 + math.exp(-beta)) / (2*beta*(2 - math.exp(-beta))))
    number_of_jumps_for_tame_kangaroo = alpha*beta

    print('b: %d, beta: %f, alpha: %f, # of jumps for tame: %d' %(b, beta, alpha, number_of_jumps_for_tame_kangaroo))

    k = random.randint(a, b)
    Q = k*P

    print('k: %d, Q: %s' %(k,Q))

    Y = Q
    z = 0
    collided = False
    
    x_tame = b*P
    total_tame_distance = 0
    tame_kangaroo_history = dict()
    tame_kangaroo_history[x_tame] = total_tame_distance

    for i in range(number_of_jumps_for_tame_kangaroo):
        x_tame, tame_jump_size = get_next_x_and_jump_size(P, x_tame, d)
        total_tame_distance += tame_jump_size
        tame_kangaroo_history[x_tame] = total_tame_distance

        if x_tame == Q:
            print('%d: REACHED Q, %s' %(i, x_tame))
            break
    distance_of_tame_kangaroo_from_origin = b + total_tame_distance # math.pow(alpha, 2)*beta

    while(not collided):
        x_wild = Y + z*P
        total_wild_distance = 0
        max_number_of_jumps_for_wild = b / alpha + number_of_jumps_for_tame_kangaroo

        for i in range(number_of_jumps_for_tame_kangaroo):
            x_wild, wild_jump_size = get_next_x_and_jump_size(P, x_wild, d)
            total_wild_distance += wild_jump_size

            if x_wild in tame_kangaroo_history:
                tame_distance = tame_kangaroo_history[x_wild]
                collided = True
                print('COLLIDED WITH X_TAME')
                computed_k = ((b + tame_distance - total_wild_distance - z) % P.order())
                print('x: %d, collision successful? %s' %(computed_k, computed_k == k % P.order()))
                break
            if total_wild_distance > distance_of_tame_kangaroo_from_origin:
                print('passed tame kangaroo')
                break
        z = random.randint(0, int(b))

start_timestamp = current_milli_time()
catch_kangaroos()
end_timestamp = current_milli_time()

print('Time elapsed', end_timestamp - start_timestamp)

b: 403813060, beta: 1.390000, alpha: 10179.544830, # of jumps for tame: 14149
k: 108302623, Q: (1029827107 : 152393852 : 1)
COLLIDED WITH X_TAME
x: 108302623, collision successful? True
('Time elapsed', 9823)
In [ ]: