kmzi5

from random import randint as rndint
from Cryptodome.Util.number import inverse
from datetime import datetime as date


def generate_L(n):
    return randint(0, n - 1)

# return elliptic curve params
def return_params():
    p = 9103
    A, B = 3, 16
    P = [4515, 5197]
    Q = [8132, 7165]
    return [p, A, B, P, Q]


# H-func
def H_function(T, L):
    x_T = T[0]
    j = lift(x_T) % L
    return j


# RHO method
def RHO_Method(E, P, Q, q):
    iter_counter = 0
    while 1:
        R, a, b = [], [], []
        L = generate_L(q)
        for j in range(0, L):
            a_j = rndint(0, q - 1)
            b_j = rndint(0, q - 1)
            R_j = a_j * P + b_j * Q
            R.append(R_j)
            a.append(a_j)
            b.append(b_j)
        a_1 = rndint(0, q - 1)
        b_1 = rndint(0, q - 1)
        T_1 = a_1 * P + b_1 * Q
        T_2 = T_1
        a_2 = a_1
        b_2 = b_1
        while 1:
            iter_counter += 1
            j = H_function(T_1, L)
            T_1 = T_1 + R[j]
            a_1 = (a_1 + a[j]) % q
            b_1 = (b_1 + b[j]) % q
            j = H_function(T_2, L)
            T_2 = T_2 + R[j]
            a_2 = (a_2 + a[j]) % q
            b_2 = (b_2 + b[j]) % q
            j = H_function(T_2, L)
            T_2 = T_2 + R[j]
            a_2 = (a_2 + a[j]) % q
            b_2 = (b_2 + b[j]) % q
            if T_1 == T_2:
                break
        if a_1 == a_2 and b_1 == b_2:
            R.clear()
            a.clear()
            b.clear()
            continue
        elif T_1 == T_2:
            a_delta = a_1 - a_2
            b_delta = (b_2 - b_1 + q) % q
            d = a_delta * inverse(b_delta, q) % q
            if Q != d * P:
                continue
            else:
                return d, iter_counter


# main
def main():
    iter_num = 0
    params = return_params()
    E = EllipticCurve(GF(params[0]), [params[1], params[2]])
    P = E(params[3][0], params[3][1])
    q = P.order()
    Q = E(params[4][0], params[4][1])
    print(E)
    print("P = {}" . format(P))
    print("Q = {}" . format(Q))
    d, iter_num = RHO_Method(E, P, Q, q)
    print("d = {}\nIterations: {}" . format(d, iter_num))



start_time = date.now()
main()
work_time = date.now() - start_time
print("Time: {}" . format(work_time))