import random
import time

# Parameters
start = 1
end = 10000000
num_people = 23
g = 2 
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 = 100  # upper bound on the step/jump size

    # Tame kangaroo
    x_tame = 0
    y_tame = birthdays[0]  # start with the first birthday as the tame kangaroo
    for _ in range(N):
        x_tame += f(y_tame, k)
        y_tame *= pow(g, f(y_tame, k), p)
        y_tame %= p

    # Wild kangaroo
    x_wild = 0
    y_wild = birthdays[-1] 

    start_time = time.time()

    # Searching for a match
    while x_wild < b - a + x_tame:
        x_wild += f(y_wild, k)
        y_wild *= pow(g, f(y_wild, k), p)
        y_wild %= p

        if y_wild == y_tame:
            end_time = time.time()
            print(f"Match found! Position: {b + x_tame - x_wild}")
            print(f"Execution time: {end_time - start_time} seconds")
            return b + x_tame - x_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(birthdays):
    print("Generated birthdays:", birthdays)
    result = kangaroo_match(birthdays, start, end)
    if result:
        print(f"[+] Secret match found: {result}")
    else:
        print("[-] The kangaroos came back empty-handed...")

# Generate random birthdays
birthdays = [random.randint(start, end) for _ in range(num_people)]

# Run the challenge
challenge(birthdays)