import sys
import os
import time
import random
import hashlib
import gmpy2
from gmpy2 import mpz
from functools import lru_cache
import multiprocessing
from multiprocessing import Pool, cpu_count

# Constants
MODULO = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
ORDER = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)
GX = gmpy2.mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
GY = gmpy2.mpz(0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

# Define Point class
class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

PG = Point(GX, GY)
ZERO_POINT = Point(0, 0)

# Function to multiply a point by 2
def multiply_by_2(P, p=MODULO):
    c = gmpy2.f_mod(3 * P.x * P.x * gmpy2.powmod(2 * P.y, -1, p), p)
    R = Point()
    R.x = gmpy2.f_mod(c * c - 2 * P.x, p)
    R.y = gmpy2.f_mod(c * (P.x - R.x) - P.y, p)
    return R

# Function to add two points
def add_points(P, Q, p=MODULO):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = gmpy2.f_mod(dy * gmpy2.invert(dx, p), p)
    R = Point()
    R.x = gmpy2.f_mod(c * c - P.x - Q.x, p)
    R.y = gmpy2.f_mod(c * (P.x - R.x) - P.y, p)
    return R

# Function to calculate Y-coordinate from X-coordinate
@lru_cache(maxsize=None)
def x_to_y(X, y_parity, p=MODULO):
    Y = gmpy2.mpz(3)
    tmp = gmpy2.mpz(1)

    while Y > 0:
        if Y % 2 == 1:
            tmp = gmpy2.f_mod(tmp * X, p)
        Y >>= 1
        X = gmpy2.f_mod(X * X, p)

    X = gmpy2.f_mod(tmp + 7, p)

    Y = gmpy2.f_div(gmpy2.add(p, 1), 4)
    tmp = gmpy2.mpz(1)

    while Y > 0:
        if Y % 2 == 1:
            tmp = gmpy2.f_mod(tmp * X, p)
        Y >>= 1
        X = gmpy2.f_mod(X * X, p)

    Y = tmp

    if Y % 2 != y_parity:
        Y = gmpy2.f_mod(-Y, p)

    return Y

# Function to compute a table of points
def compute_point_table():
    points = [PG]
    for k in range(255):
        points.append(multiply_by_2(points[k]))
    return points

POINTS_TABLE = compute_point_table()

# Global event to signal all processes to stop
STOP_EVENT = multiprocessing.Event()

# Function to check and compare points for potential solutions
def check(P, Pindex, DP_rarity, A, Ak, B, Bk):
    check = gmpy2.f_mod(P.x, DP_rarity)
    if check == 0:
        message = f"\r[+] [Pindex]: {mpz(Pindex)}"
        messages = []
        messages.append(message)
        output = "\033[01;33m" + ''.join(messages) + "\r"
        sys.stdout.write(output)
        sys.stdout.flush()
        A.append(mpz(P.x))
        Ak.append(mpz(Pindex))
        return comparator(A, Ak, B, Bk)
    else:
        return False

# Function to compare two sets of points and find a common point
def comparator(A, Ak, B, Bk):
    global STOP_EVENT
    result = set(A).intersection(set(B))

    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        difference = Ak[sol_kt] - Bk[sol_kw]
        HEX = "%064x" % difference
        t = time.ctime()
        total_time = time.time() - starttime
        print(f"\033[32m[+] PUZZLE SOLVED: {t}, total time: {total_time:.2f} sec \033[0m")
        print(f"\033[32m[+] WIF: \033[32m {HEX} \033[0m")
        with open("KEYFOUNDKEYFOUND.txt", "a") as file:
            file.write("\n\nSOLVED " + t)
            file.write(f"\nTotal Time: {total_time:.2f} sec")
            file.write("\nPrivate Key (decimal): " + str(difference))
            file.write("\nPrivate Key (hex): " + HEX)
            file.write(
                "\n-------------------------------------------------------------------------------------------------------------------------------------\n"
            )

        STOP_EVENT.set()  # Set the stop event to signal all processes

# Memoization for point multiplication
ECMULTIPLY_MEMO = {}

# Function to multiply a point by a scalar
def ecmultiply(k, P=PG, p=MODULO):
    if k == 0:
        return ZERO_POINT
    elif k == 1:
        return P
    elif k % 2 == 0:
        if k in ECMULTIPLY_MEMO:
            return ECMULTIPLY_MEMO[k]
        else:
            result = ecmultiply(k // 2, multiply_by_2(P, p), p)
            ECMULTIPLY_MEMO[k] = result
            return result
    else:
        return add_points(P, ecmultiply((k - 1) // 2, multiply_by_2(P, p), p))

# Recursive function to multiply a point by a scalar
def mulk(k, P=PG, p=MODULO):
    if k == 0:
        return ZERO_POINT
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, multiply_by_2(P, p), p)
    else:
        return add_points(P, mulk((k - 1) // 2, multiply_by_2(P, p), p))

# Generate a list of powers of two for faster access
@lru_cache(maxsize=None)
def generate_powers_of_two(hop_modulo):
    return [mpz(1 << pw) for pw in range(hop_modulo)]

# Worker function for point search
def search_worker(
    Nt, Nw, puzzle, kangaroo_power, starttime, lower_range_limit, upper_range_limit
):
    global STOP_EVENT
    #Random seed Config
    #constant_prefix = b''  #back to no constant
    #constant_prefix = b'\xbc\x9b\x8cd\xfc\xa1?\xcf' #Puzzle 50 seed - 10s
    constant_prefix = b'\xbc\x9b\x8cd\xfc\xa1?\xcf'
    prefix_length = len(constant_prefix)
    length = 8
    ending_length = length - prefix_length
    with open("/dev/urandom", "rb") as urandom_file:
        ending_bytes = urandom_file.read(ending_length)
    random_bytes = constant_prefix + ending_bytes
    print(f"[+] [Random seed]: {random_bytes}")
    random.seed(random_bytes) 
    t = [
        mpz(
            lower_range_limit
            + mpz(random.randint(0, upper_range_limit - lower_range_limit))
        )
        for _ in range(Nt)
    ]
    T = [mulk(ti) for ti in t]
    dt = [mpz(0) for _ in range(Nt)]
    w = [
        mpz(random.randint(0, upper_range_limit - lower_range_limit)) for _ in range(Nt)
    ]
    W = [add_points(W0, mulk(wk)) for wk in w]
    dw = [mpz(0) for _ in range(Nw)]

    Hops, Hops_old = 0, 0

    oldtime = time.time()
    starttime = oldtime

    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = powers_of_two[pw]
            solved = check(T[k], t[k], DP_rarity, T, t, W, w)
            if solved:
                STOP_EVENT.set()
                break
            t[k] = mpz(t[k]) + dt[k]  # Use mpz here
            T[k] = add_points(POINTS_TABLE[pw], T[k])

        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = powers_of_two[pw]
            solved = check(W[k], w[k], DP_rarity, W, w, T, t)
            if solved:
                STOP_EVENT.set()
                break
            w[k] = mpz(w[k]) + dw[k]  # Use mpz here
            W[k] = add_points(POINTS_TABLE[pw], W[k])

        if STOP_EVENT.is_set():
            break


# Main script
if __name__ == "__main__":
    os.system("clear")
    t = time.ctime()
    sys.stdout.write("\033[01;33m")
    sys.stdout.write(f"[+] [Kangaroo]: {t}" + "\n")
    sys.stdout.flush()

    # Configuration for the puzzle
    puzzle = 50
    compressed_public_key = "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"  # Puzzle 50
    lower_range_limit = 2 ** (puzzle - 1)
    upper_range_limit = (2 ** puzzle) - 1 
    kangaroo_power = puzzle // 8
    Nt = Nw = (2 ** kangaroo_power // puzzle) * puzzle + 8
    DP_rarity = 8 * puzzle
    hop_modulo = (puzzle // 2) + 8

    # Precompute powers of two for faster access
    powers_of_two = generate_powers_of_two(hop_modulo)

    T, t, dt = [], [], []
    W, w, dw = [], [], []

    if len(compressed_public_key) == 66:
        X = mpz(compressed_public_key[2:66], 16)
        Y = x_to_y(X, mpz(compressed_public_key[:2]) - 2)
    else:
        print("[error] pubkey len(66/130) invalid!")

    print(f"[+] [Puzzle]: {puzzle}")
    print(f"[+] [Lower range limit]: {lower_range_limit}")
    print(f"[+] [Upper range limit]: {upper_range_limit}")
    print("[+] [Xcoordinate]: %064x" % X)
    print("[+] [Ycoordinate]: %064x" % Y)

    W0 = Point(X, Y)
    starttime = oldtime = time.time()

    Hops = 0

    process_count = cpu_count()
    print(f"[+] Using {process_count} CPU cores for parallel search")

    # Create a pool of worker processes
    pool = Pool(process_count)
    results = pool.starmap(
        search_worker,
        [
            (
                Nt,
                Nw,
                puzzle,
                kangaroo_power,
                starttime,
                lower_range_limit,
                upper_range_limit,
            )
        ]
        * process_count,
    )
    pool.close()
    pool.join()