Quote from: nomachine on Today at 11:00:51 AM

Quote from: Denis_Hitov on October 11, 2023, 08:37:34 PM

Quote from: nomachine on October 11, 2023, 10:17:14 AM

Quote from: dextronomous on October 11, 2023, 10:14:23 AM

PUZZLE SOLVED: Wed Oct 11 12:13:21 2023, total time: 13.47 sec

WIF: -0000000000000000000000000000000000000000000000000022bd43c2e9354

nice catching again nomachine, is this programmable for 120th and up

Yes.
It takes about 3 minutes to start solving Puzzle 130 on my 12 Core - but will start.

Here is code for Puzzle130

Code:

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()
   pid = os.getpid() # Get the process ID
   core_number = pid % cpu_count() # Calculate the CPU core number
   total_time = time.time() - starttime
   print(f"\033[32m[+] PUZZLE SOLVED: {t}, total time: {total_time:.2f} sec, Core: {core_number+1:02} \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
   pid = os.getpid()
   core_number = pid % cpu_count()
   #Random seed Config
   #constant_prefix = b'' #back to no constant
   #constant_prefix = b'\xbc\x9b\x8cd\xfc\xa1?\xcf' #Puzzle 50 seed - 10-18s
   constant_prefix = b'\xbc\x9b'
   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"[+] [Core]: {core_number+1:02}, [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 = 130
   compressed_public_key = "03633cbe3ec02b9401c5effa144c5b4d22f87940259634858fc7e59b1c09937852" # Puzzle 130
   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()

I put only 2 bytes as a constant - the rest will be randomized through all CPU cores, since we don't know what the seed for 130 is. . .
constant_prefix = b'\xbc\x9b'
constant_prefix = b'' is all random

ON the smaller puzzles it is easy to guess what the seed is. You need to restart and restart app and you will find out which is the fastest seed by repetition. The script will show exactly which seed and which core hit the WIF. You can experiment with different ones as you like.

FileNotFoundError: [Errno 2] No such file or directory: '/dev/urandom'

if you dont have '/dev/urandom' here is script without '/dev/urandom'

Code:

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()
   pid = os.getpid() # Get the process ID
   core_number = pid % cpu_count() # Calculate the CPU core number
   total_time = time.time() - starttime
   print(f"\033[32m[+] PUZZLE SOLVED: {t}, total time: {total_time:.2f} sec, Core: {core_number+1:02} \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
   pid = os.getpid()
   core_number = pid % cpu_count()
   #Random seed Config
   #constant_prefix = b'' #back to no constant
   #constant_prefix = b'\xbc\x9b\x8cd\xfc\xa1?\xcf' #Puzzle 50 seed - 10-18s
   constant_prefix = b'\xbc\x9b\x8cd'
   prefix_length = len(constant_prefix)
   length = 8
   ending_length = length - prefix_length
   ending_bytes = os.urandom(ending_length)
   random_bytes = constant_prefix + ending_bytes
   print(f"[+] [Core]: {core_number+1:02}, [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 = 130
   compressed_public_key = "03633cbe3ec02b9401c5effa144c5b4d22f87940259634858fc7e59b1c09937852" # Puzzle 130
   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()

Now this is an error.

NameError: name 'W0' is not defined