Topic: Bitcoin puzzle transaction ~32 BTC prize to who solves it - page 40. (Read 245388 times)

import random
import time

# Parameters
start = 1
end = 100000  # Reduced range for better chance of finding matches
num_people = 23
g = 2  # Base for the kangaroo jumps
p = 1000000007  # Large prime modulus

# Function for generating random jumps (analogous to a hash function)
def f(x, k):
    return random.randint(1, k)

# Pollard's Kangaroo-like method for matching birthdays
def kangaroo_match(birthdays, start, end):
    a = start
    b = end
    N = len(birthdays)
    k = 10  # Upper bound on the step/jump size

    # Tame kangaroo setup
    x_tame = 0
    y_tame = birthdays[0]  # Start with the first birthday as the tame kangaroo
    visited = {y_tame}  # Track visited positions

    for _ in range(N):
        # Make a jump with the tame kangaroo
        x_tame += f(y_tame, k)
        y_tame = (y_tame + random.randint(1, 10)) % end  # Jump in a reduced range
        visited.add(y_tame)

        # Check if we have a match
        if y_tame in birthdays:
            print(f"Match found by tame kangaroo at: {y_tame}")
            return y_tame

    # Wild kangaroo setup
    x_wild = 0
    y_wild = random.randint(start, end)  # Start wild kangaroo with a random position

    start_time = time.time()

    # Searching for a match
    while x_wild < b - a + x_tame:
        # Make a jump with the wild kangaroo
        x_wild += f(y_wild, k)
        y_wild = (y_wild + random.randint(1, 10)) % end  # Jump in a reduced range

        if y_wild in visited:
            print(f"Match found by wild kangaroo at: {y_wild}")
            end_time = time.time()
            print(f"Execution time: {end_time - start_time} seconds")
            return y_wild

    end_time = time.time()
    print(f"Execution time: {end_time - start_time} seconds")
    print("No match found.")
    return None

# Challenge function to test the search
def challenge():
    # Generate random birthdays
    birthdays = [random.randint(start, end) for _ in range(num_people)]
    print("Generated birthdays:", birthdays)

    # Run kangaroo match
    match = kangaroo_match(birthdays, start, end)
    if match:
        print(f"[+] Secret match found: {match}")
    else:
        print("[-] The kangaroos came back empty-handed...")

# Run the challenge
challenge()