Topic: Pollard's kangaroo ECDLP solver - page 8. (Read 55445 times)

void Kangaroo::CreateJumpTable() {

#ifdef USE_SYMMETRY
  int jumpBit = rangePower / 2;
#else
  int jumpBit = rangePower / 2 + 1;
#endif

  if(jumpBit > 128) jumpBit = 128;
  int maxRetry = 100;
  bool ok = false;
  double distAvg;
  double maxAvg = pow(2.0,(double)jumpBit - 0.95);
  double minAvg = pow(2.0,(double)jumpBit - 1.05);
  //::printf("Jump Avg distance min: 2^%.2f\n",log2(minAvg));
  //::printf("Jump Avg distance max: 2^%.2f\n",log2(maxAvg));
 
  // Kangaroo jumps
  // Constant seed for compatibilty of workfiles
  rseed(0x600DCAFE);

import sys
import io
import random
import math
import gmpy2
from gmpy2 import mpz
from functools import lru_cache
from multiprocessing import Pool, cpu_count

modulo = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
order = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)
Gx = gmpy2.mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
Gy = gmpy2.mpz(0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)


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


PG = Point(Gx, Gy)
Z = Point(0, 0)  # zero-point, infinite in real x,y-plane


def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R


def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R


@lru_cache(maxsize=None)
def X2Y(X, y_parity, p=modulo):
    Y = 3
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    X = (tmp + 7) % p

    Y = (p + 1) // 4
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    Y = tmp

    if Y % 2 != y_parity:
        Y = -Y % p

    return Y


def compute_P_table():
    P = [PG]
    for k in range(255):
        P.append(mul2(P[k]))
    return P


P = compute_P_table()

os.system("clear")
t = time.ctime()
sys.stdout.write("\033[01;33m")
sys.stdout.write("################################################" + "\n")
sys.stdout.write("Pollard-kangaroo PrivKey Recovery Tool multicore" + "\n")
sys.stdout.write("################################################" + "\n")
sys.stdout.write(t + "\n")
sys.stdout.write("P-table prepared" + "\n")
sys.stdout.write("tame and wild herds kangaroos is being prepared" + "\n")
sys.stdout.flush()


def comparator(A, Ak, B, Bk):
    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  # Convert to a hexadecimal string
        t = time.ctime()
        total_time = time.time() - starttime
        print("\033[01;33mSOLVED:", t, f"total time: {total_time:.2f} sec", HEX, "\n")
        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"
            )

    return result

    """        
        return True
    else:
        return False
    """

# Batch writing function
def batch_write_data_to_file(data, file_path, batch_size=5000):
    with open(file_path, "a", buffering=1024 * 1024 * 1024) as fp:
        for i in range(0, len(data), batch_size):
            batch = data[i : i + batch_size]
            fp.writelines(batch)


# Function to check and write data to file
def check(
    P, Pindex, DP_rarity, file2save, A, Ak, B, Bk, buffer_size=1024 * 1024 * 1024
):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        data_to_write = ["%064x %d\n" % (P.x, Pindex)]
        ## YOU DONT USE TAME AND WILD IN SCRIPT! SO FOR WHAT IMPLEMENT IT? IT TAKING TIME AND MEMORY
        """
        batch_write_data_to_file(data_to_write, file2save)  # Batch write data to file
        # Print the public key
        message = "\rPublic key: {:064x}".format(P.x)
        sys.stdout.write("\033[01;33m")
        sys.stdout.write(message + "\r")
        sys.stdout.flush()
        """
        return comparator(A, Ak, B, Bk)
    else:
        return False


def save2file(path, mode, data, buffer_size=1024 * 1024 * 1024):
    with open(path, mode, encoding="utf-8") as fp:
        if isinstance(data, (list, tuple, dict, set)):
            for line in data:
                if isinstance(line, str):
                    fp.write(line)
                elif isinstance(line, int):
                    fp.write(str(line))
        elif isinstance(data, (str, int)):
            fp.write(str(data))


# Memoization for ecmultiply
ecmultiply_memo = {}


def ecmultiply(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        if k in ecmultiply_memo:
            return ecmultiply_memo[k]
        else:
            result = ecmultiply(k // 2, mul2(P, p), p)
            ecmultiply_memo[k] = result
            return result
    else:
        return add(P, ecmultiply((k - 1) // 2, mul2(P, p), p))


def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p))


def search(Nt, Nw, puzzle, kangoo_power, starttime):
    # NOT NECESSARY - TAKING TIME AS MULTIPLY BY PROCESS -> THING AS MINIMALISED TIME FOR OPERATION -> BETTER JOIN FOR ALL PROCESSING Moved !
    """
    DP_rarity = 1 << ((puzzle - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((puzzle - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    """
    
    for k in range(Nt):
        t.append((3 << (puzzle - 2)) + random.randint(1, (2 ** (puzzle - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
        
    for k in range(Nw):
        w.append(random.randint(1, (1 << (puzzle - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)
    
    #oldtime = time.time()  -> NOT USING TAKING TIME
    Hops, Hops_old = 0, 0
    #t0 = time.time()         -> NOT USING TAKING TIME
    oldtime = time.time()
    starttime = oldtime
    while True:
        # THIS FUNCTION CHANGE FOR THREAD
        
        #THREAD ONE
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                return "sol. time: %.2f sec" % (time.time() - starttime)
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
        
        #THREAD 2    
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                return "sol. time: %.2f sec" % (time.time() - starttime)
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])

# DATA SETS AND IMPORTANT INFORMATION -> THINK ABOUT IT AS MINIMALISED OPERATION.

puzzle = 50
compressed_public_key = (
    "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"  # Puzzle 50
)
kangoo_power = 10  # For Puzzle 50-56 use 9 to 11, for Puzzle 60-80 use 14 to 16 / 24 cores or above preferred
Nt = Nw = 2**kangoo_power

# MOVED FROM SEARCH DEF
DP_rarity = 1 << ((puzzle - 2 * kangoo_power) // 2 - 2)
hop_modulo = ((puzzle - 1) // 2) + kangoo_power
T, t, dt = [], [], []
W, w, dw = [], [], []

for k in range(Nt):
    t.append((3 << (puzzle - 2)) + random.randint(1, (2 ** (puzzle - 1))))
    T.append(mulk(t[k]))
    dt.append(0)
    
# check format pubkey
if len(compressed_public_key) == 66:
    X = int(compressed_public_key[2:66], 16)
    # calculation Y from X if pubkey is compressed
    Y = X2Y(X, gmpy2.mpz(compressed_public_key[:2]) - 2)
else:
    print("[error] pubkey len(66/130) invalid!")

print(f"[Puzzle]: {puzzle}")
print("[Xcoordinate]: %064x" % X)
print("[Ycoordinate]: %064x" % Y)

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

Hops = 0
random.seed()

hops_list = []
N_tests = kangoo_power

## YOU DONT USE TAME AND WILD IN SCRIPT! SO FOR WHAT IMPLEMENT IT? IT TAKING TIME AND MEMORY
"""
for k in range(N_tests):
    # Create empty 'tame.txt' and 'wild.txt' files for each iteration
    save2file("tame.txt", "w", "")
    save2file("wild.txt", "w", "")
"""

def parallel_search(process_count, Nt, Nw, puzzle, kangoo_power, starttime):
    pool = Pool(process_count)
    results = pool.starmap(
        search, [(Nt, Nw, puzzle, kangoo_power, starttime)] * process_count
    )
    pool.close()
    pool.join()
    return results


if __name__ == "__main__":
    process_count = cpu_count()  # Use all available CPU cores
    print(f"Using {process_count} CPU cores for parallel search.")
    results = parallel_search(process_count, Nt, Nw, puzzle, kangoo_power, starttime)
    for result in results:
        print(result)

################################################
Pollard-kangaroo PrivKey Recovery Tool multicore
################################################
Sun Sep 10 13:42:36 2023
P-table prepared
tame and wild herds kangaroos is being prepared
[Puzzle]: 50
[Xcoordinate]: f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6
[Ycoordinate]: eb3dfcc04c320b55c529291478550be6072977c0c86603fb2e4f5283631064fb
Using 4 CPU cores for parallel search.
SOLVED: Sun Sep 10 13:44:06 2023 total time: 89.33 sec -0000000000000000000000000000000000000000000000000022bd43c2e9354

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

modulo = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
order = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)
Gx = gmpy2.mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
Gy = gmpy2.mpz(0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)


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


PG = Point(Gx, Gy)
Z = Point(0, 0)  # zero-point, infinite in real x,y-plane


def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R


def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R


@lru_cache(maxsize=None)
def X2Y(X, y_parity, p=modulo):
    Y = 3
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    X = (tmp + 7) % p

    Y = (p + 1) // 4
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    Y = tmp

    if Y % 2 != y_parity:
        Y = -Y % p

    return Y


def compute_P_table():
    P = [PG]
    for k in range(255):
        P.append(mul2(P[k]))
    return P


P = compute_P_table()

os.system("clear")
t = time.ctime()
sys.stdout.write("\033[01;33m")
sys.stdout.write("################################################" + "\n")
sys.stdout.write("Pollard-kangaroo PrivKey Recovery Tool multicore" + "\n")
sys.stdout.write("################################################" + "\n")
sys.stdout.write(t + "\n")
sys.stdout.write("P-table prepared" + "\n")
sys.stdout.write("tame and wild herds kangaroos is being prepared" + "\n")
sys.stdout.flush()


def comparator(A, Ak, B, Bk):
    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  # Convert to a hexadecimal string
        t = time.ctime()
        total_time = time.time() - starttime
        print("\033[01;33mSOLVED:", t, f"total time: {total_time:.2f} sec", HEX, "\n")
        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"
            )
        return True
    else:
        return False


# Batch writing function
def batch_write_data_to_file(data, file_path, batch_size=5000):
    with open(file_path, "a", buffering=1024 * 1024 * 1024) as fp:
        for i in range(0, len(data), batch_size):
            batch = data[i : i + batch_size]
            fp.writelines(batch)


# Function to check and write data to file
def check(
    P, Pindex, DP_rarity, file2save, A, Ak, B, Bk, buffer_size=1024 * 1024 * 1024
):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        data_to_write = ["%064x %d\n" % (P.x, Pindex)]
        batch_write_data_to_file(data_to_write, file2save)  # Batch write data to file
        # Print the public key
        message = "\rPublic key: {:064x}".format(P.x)
        sys.stdout.write("\033[01;33m")
        sys.stdout.write(message + "\r")
        sys.stdout.flush()
        return comparator(A, Ak, B, Bk)
    else:
        return False


def save2file(path, mode, data, buffer_size=1024 * 1024 * 1024):
    with open(path, mode, encoding="utf-8") as fp:
        if isinstance(data, (list, tuple, dict, set)):
            for line in data:
                if isinstance(line, str):
                    fp.write(line)
                elif isinstance(line, int):
                    fp.write(str(line))
        elif isinstance(data, (str, int)):
            fp.write(str(data))


# Memoization for ecmultiply
ecmultiply_memo = {}


def ecmultiply(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        if k in ecmultiply_memo:
            return ecmultiply_memo[k]
        else:
            result = ecmultiply(k // 2, mul2(P, p), p)
            ecmultiply_memo[k] = result
            return result
    else:
        return add(P, ecmultiply((k - 1) // 2, mul2(P, p), p))


def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p))


def search(Nt, Nw, puzzle, kangoo_power, starttime):
    DP_rarity = 1 << ((puzzle - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((puzzle - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    for k in range(Nt):
        t.append((3 << (puzzle - 2)) + random.randint(1, (2 ** (puzzle - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
    for k in range(Nw):
        w.append(random.randint(1, (1 << (puzzle - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)
    oldtime = time.time()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    oldtime = time.time()
    starttime = oldtime
    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                return "sol. time: %.2f sec" % (time.time() - starttime)
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                return "sol. time: %.2f sec" % (time.time() - starttime)
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])


puzzle = 50
compressed_public_key = (
    "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"  # Puzzle 50
)
kangoo_power = 11  # For Puzzle 50-56 use 9 to 11, for Puzzle 60-80 use 14 to 16 / 24 cores or above preferred
Nt = Nw = 2**kangoo_power
# check format pubkey
if len(compressed_public_key) == 66:
    X = int(compressed_public_key[2:66], 16)
    # calculation Y from X if pubkey is compressed
    Y = X2Y(X, gmpy2.mpz(compressed_public_key[:2]) - 2)
else:
    print("[error] pubkey len(66/130) invalid!")

print(f"[Puzzle]: {puzzle}")
print("[Xcoordinate]: %064x" % X)
print("[Ycoordinate]: %064x" % Y)

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

Hops = 0
random.seed()

hops_list = []
N_tests = kangoo_power

for k in range(N_tests):
    # Create empty 'tame.txt' and 'wild.txt' files for each iteration
    save2file("tame.txt", "w", "")
    save2file("wild.txt", "w", "")


def parallel_search(process_count, Nt, Nw, puzzle, kangoo_power, starttime):
    pool = Pool(process_count)
    results = pool.starmap(
        search, [(Nt, Nw, puzzle, kangoo_power, starttime)] * process_count
    )
    pool.close()
    pool.join()
    return results


if __name__ == "__main__":
    process_count = cpu_count()  # Use all available CPU cores
    print(f"Using {process_count} CPU cores for parallel search.")
    results = parallel_search(process_count, Nt, Nw, puzzle, kangoo_power, starttime)
    for result in results:
        print(result)

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

modulo = gmpy2.mpz(115792089237316195423570985008687907853269984665640564039457584007908834671663)
order = gmpy2.mpz(115792089237316195423570985008687907852837564279074904382605163141518161494337)
Gx = gmpy2.mpz(55066263022277343669578718895168534326250603453777594175500187360389116729240)
Gy = gmpy2.mpz(32670510020758816978083085130507043184471273380659243275938904335757337482424)

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

PG = Point(Gx, Gy)
Z = Point(0, 0)  # zero-point, infinite in real x,y-plane

def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

@lru_cache(maxsize=None)
def X2Y(X, y_parity, p=modulo):
    Y = 3
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    X = (tmp + 7) % p

    Y = (p + 1) // 4
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    Y = tmp

    if Y % 2 != y_parity:
        Y = -Y % p

    return Y

def compute_P_table():
    P = [PG]
    for k in range(255):
        P.append(mul2(P[k]))
    return P

P = compute_P_table()

os.system('clear')
t = time.ctime()
sys.stdout.write("\033[01;33m")
sys.stdout.write(t + "\n")
sys.stdout.write("P-table prepared" + "\n")
sys.stdout.write("tame and wild herds is being prepared" + "\n")
sys.stdout.flush()

def comparator(A, Ak, B, Bk):
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        print('total time: %.2f sec' % (time.time() - starttime))
        difference = Ak[sol_kt] - Bk[sol_kw]
        HEX = "%064x" % difference  # Convert to a hexadecimal string
        t = time.ctime()
        print('SOLVED:', t, difference)
        with open("KEYFOUNDKEYFOUND.txt", 'a') as file:
            file.write('\n\nSOLVED ' + t)
            file.write('\nPrivate Key (decimal): ' + str(difference))
            file.write('\nPrivate Key (hex): ' + HEX)
            file.write('\n-------------------------------------------------------------------------------------------------------------------------------------\n')
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, file2save, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        with open(file2save, 'a') as file:
            file.write(('%064x %d' % (P.x, Pindex)) + "\n")
        # Print the public key
        message = "\rPublic key: {:064x}".format(P.x)
        sys.stdout.write("\033[01;33m")
        sys.stdout.write(message)
        sys.stdout.flush()
        return comparator(A, Ak, B, Bk)
    else:
        return False

# Memoization for ecmultiply
ecmultiply_memo = {}

def ecmultiply(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        if k in ecmultiply_memo:
            return ecmultiply_memo[k]
        else:
            result = ecmultiply(k // 2, mul2(P, p), p)
            ecmultiply_memo[k] = result
            return result
    else:
        return add(P, ecmultiply((k - 1) // 2, mul2(P, p), p))

def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p))

def search(Nt, Nw, puzzle, kangoo_power, starttime):
    DP_rarity = 1 << ((puzzle - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((puzzle - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    for k in range(Nt):
        t.append((3 << (puzzle - 2)) + random.randint(1, (1 << (puzzle - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
    for k in range(Nw):
        w.append(random.randint(1, (1 << (puzzle - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)
    oldtime = time.time()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    oldtime = time.time()
    starttime = oldtime
    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])

puzzle = 50
compressed_public_key = "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"  # Puzzle 50
kangoo_power = 10 #For Puzzle 50-56 use 9 to 11, for Puzzle 60-80 use 14 to 16 / 24 cores or above preferred
Nt = Nw = 2 ** kangoo_power
X = int(compressed_public_key, 16)
Y = X2Y(X % (2 ** 256), X >> 256)
if Y % 2 != (X >> 256) % 2:
    Y = modulo - Y
X = X % (2 ** 256)
W0 = Point(X, Y)
starttime = oldtime = time.time()

Hops = 0
random.seed()

hops_list = []
N_tests = kangoo_power

for k in range(N_tests):
    buffer_size = 1024 * 1024 * 1024  # 1024 MB in bytes
    with open("tame.txt", 'w', buffering=buffer_size) as tame_file, open("wild.txt", 'w', buffering=buffer_size) as wild_file:
        tame_file.write('')
        wild_file.write('')

def parallel_search(process_count, Nt, Nw, puzzle, kangoo_power, starttime):
    pool = Pool(process_count)
    results = pool.starmap(search, [(Nt, Nw, puzzle, kangoo_power, starttime)] * process_count)
    pool.close()
    pool.join()
    return results

if __name__ == '__main__':
    process_count = cpu_count()  # Use all available CPU cores
    print(f"Using {process_count} CPU cores for parallel search.")
    results = parallel_search(process_count, Nt, Nw, puzzle, kangoo_power, starttime)
    for result in results:
        print(result)

import time
import random
import gmpy2
from functools import lru_cache
import multiprocessing
from tqdm import tqdm

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

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

PG = Point(Gx, Gy)
Z = Point(0, 0)  # zero-point, infinite in real x,y-plane

def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

@lru_cache(maxsize=None)
def X2Y(X, p=modulo):
    if p % 4 != 3:
        print('prime must be 3 modulo 4')
        return 0
    X = (X ** 3 + 7) % p
    pw = (p + 1) // 4
    Y = 1
    tmp = X
    for w in range(256):
        if (pw >> w) & 1 == 1:
            Y = (Y * tmp) % p
        tmp = pow(tmp, 2, p)
    return Y

def compute_P_table():
    P = [PG]
    for k in range(255):
        P.append(mul2(P[k]))
    return P

P = compute_P_table()

print('P-table prepared')

def comparator(A, Ak, B, Bk):
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        d = Ak[sol_kt] - Bk[sol_kw]
        print('SOLVED:', d)
        with open("results.txt", 'a') as file:
            file.write(('%d' % (Ak[sol_kt] - Bk[sol_kw])) + "\n")
            file.write("---------------\n")
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, file2save, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        with open(file2save, 'a') as file:
            file.write(('%064x %d' % (P.x, Pindex)) + "\n")
        return comparator(A, Ak, B, Bk)
    else:
        return False

def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p))

def search(process_id, Nt, Nw, problem, kangoo_power, starttime):
    DP_rarity = 1 << ((problem - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((problem - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    for k in range(Nt):
        t.append((3 << (problem - 2)) + random.randint(1, (1 << (problem - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
    for k in range(Nw):
        w.append(random.randint(1, (1 << (problem - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)

    print('tame and wild herds are prepared')

    oldtime = time.time()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    starttime = oldtime = time.time()

    total_tame_iterations = Nt * (problem - 2 * kangoo_power - 2)
    total_wild_iterations = Nw * (problem - 2 * kangoo_power - 2)
    total_iterations = total_tame_iterations + total_wild_iterations

    pbar_t = tqdm(total=total_tame_iterations, desc=f"Process {process_id}: tame", position=process_id, leave=False, ncols=50, bar_format="{desc:<0}|{bar} | {percentage:3.2f}% | ")
    pbar_w = tqdm(total=total_wild_iterations, desc=f"Process {process_id}: wild", position=process_id, leave=False, ncols=50, bar_format="{desc:<0}|{bar} | {percentage:3.2f}% | ")

    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                pbar_t.close()
                pbar_w.close()
                elapsed_time_t = time.time() - starttime
                percentage_completed = (Hops / total_iterations) * 100
                print(f'Process {process_id}: tame completed: %.2f%%' % (percentage_completed % 100))
                return f'Process {process_id}: tame sol. time: %.2f sec' % elapsed_time_t
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
            pbar_t.update(1)

        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                pbar_t.close()
                pbar_w.close()
                elapsed_time_w = time.time() - starttime
                percentage_completed = (Hops / total_iterations) * 100
                print(f'Process {process_id}: wild completed: %.2f%%' % (percentage_completed % 100))
                return f'Process {process_id}: wild sol. time: %.2f sec' % elapsed_time_w
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])
            pbar_w.update(1)

def search_wrapper(args):
    return search(*args)

if __name__ == "__main__":
    start = 2147483647
    end = 4294967295
    search_range = end - start + 1
    problem = search_range.bit_length()

    compressed_public_key = "0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69" #Puzzle 32
    kangoo_power = 3
    Nt = Nw = 2 ** kangoo_power

    X = int(compressed_public_key, 16)
    Y = X2Y(X % (2 ** 256))
    if Y % 2 != (X >> 256) % 2:
        Y = modulo - Y
    X = X % (2 ** 256)
    W0 = Point(X, Y)
    starttime = oldtime = time.time()

    num_cpus = multiprocessing.cpu_count()
    N_tests = num_cpus  # Use the number of CPU cores as the number of tests

    args = [(i, Nt, Nw, problem, kangoo_power, starttime) for i in range(N_tests)]

    with multiprocessing.Pool(processes=N_tests) as pool:
        results = list(tqdm(pool.imap(search_wrapper, args), total=N_tests, bar_format="{desc:<0}|{bar} | {percentage:3.2f}% | ", ncols=50))

    total_time = sum(float(result.split(': ')[-1][:-4]) for result in results if result is not None)
    print('Average time to solve: %.2f sec' % (total_time / N_tests))

P-table prepared
|                                       | 0.00% | tame and wild herds are prepared
Process 0: wild|                        | 0.00% | tame and wild herds are prepared
tame and wild herds are prepared
tame and wild herds are prepared
Process 0: wild|                        | 0.00% | SOLVED: -3093472814
Process 0: wild completed: 61.46%                 
|█████████▎                            | 25.00% | SOLVED: -3093472814
Process 1: wild|                        | 0.00% | Process 2: wild completed: 28.39%
Process 2: wild|                        | 0.00% | SOLVED: 3093472814
Process 1: tame|                        | 0.00% | Process 1: tame completed: 34.64%
|██████████████████▌                   | 50.00% | SOLVED: -3093472814
Process 3: wild|                        | 0.00% | Process 3: wild completed: 19.01%
|████████████████████████████████████ | 100.00% |
Average time to solve: 1.53 sec         | 0.00% |

import time
import random
import gmpy2
from functools import lru_cache
import multiprocessing

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

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

PG = Point(Gx, Gy)
Z = Point(0, 0)  # zero-point, infinite in real x,y-plane

def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

@lru_cache(maxsize=None)
def X2Y(X, p=modulo):
    if p % 4 != 3:
        print('prime must be 3 modulo 4')
        return 0
    X = (X ** 3 + 7) % p
    pw = (p + 1) // 4
    Y = 1
    tmp = X
    for w in range(256):
        if (pw >> w) & 1 == 1:
            Y = (Y * tmp) % p
        tmp = pow(tmp, 2, p)
    return Y

def compute_P_table():
    P = [PG]
    for k in range(255):
        P.append(mul2(P[k]))
    return P

P = compute_P_table()

print('P-table prepared')

def comparator(A, Ak, B, Bk):
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        print('total time: %.2f sec' % (time.time() - starttime))
        d = Ak[sol_kt] - Bk[sol_kw]
        print('SOLVED:', d)
        with open("results.txt", 'a') as file:
            file.write(('%d' % (Ak[sol_kt] - Bk[sol_kw])) + "\n")
            file.write("---------------\n")
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, file2save, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        with open(file2save, 'a') as file:
            file.write(('%064x %d' % (P.x, Pindex)) + "\n")
        return comparator(A, Ak, B, Bk)
    else:
        return False

def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p))

def search(process_id, Nt, Nw, problem, kangoo_power, starttime):
    DP_rarity = 1 << ((problem - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((problem - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    for k in range(Nt):
        t.append((3 << (problem - 2)) + random.randint(1, (1 << (problem - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
    for k in range(Nw):
        w.append(random.randint(1, (1 << (problem - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)
    print('tame and wild herds are prepared')
    oldtime = time.time()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    oldtime = time.time()
    starttime = oldtime
    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])
        t1 = time.time()
        if (t1 - t0) > 5:
            print('%.3f h/s' % ((Hops - Hops_old) / (t1 - t0)))
            t0 = t1
            Hops_old = Hops

start = 2147483647
end = 4294967295
search_range = end - start + 1
problem = search_range.bit_length()

compreessed_public_key = "0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69" #Puzzle 32
kangoo_power = 3
Nt = Nw = 2 ** kangoo_power

X = int(compreessed_public_key, 16)
Y = X2Y(X % (2 ** 256))
if Y % 2 != (X >> 256) % 2:
    Y = modulo - Y
X = X % (2 ** 256)
W0 = Point(X, Y)
starttime = oldtime = time.time()

Hops = 0
random.seed()

hops_list = []
N_tests = 3

def search_wrapper(process_id):
    return search(process_id, Nt, Nw, problem, kangoo_power, starttime)

if __name__ == "__main__":
    num_cpus = multiprocessing.cpu_count()
    N_tests = num_cpus  # Use the number of CPU cores as the number of tests

    with multiprocessing.Pool(processes=N_tests) as pool:
        results = pool.map(search_wrapper, range(N_tests))

    for result in results:
        print(result)
        M, D = 0, 0
        if len(hops_list) > 0:
            M = sum(hops_list) * 1.0 / len(hops_list)
            D = sum((xi - M) ** 2 for xi in hops_list) * 1.0 / len(hops_list)
        print(M, '+/-', (D / (len(hops_list) - 1)) ** 0.5)
        print('Average time to solve: %.2f sec' % ((time.time() - starttime) / N_tests))