import gmpy2

def gen_tame_wild(lower_bound, upper_bound, herd_size, N):

    tame = []
    wild = []
    (lower, lower_idx), (upper, upper_idx) = closest_triangular_numbers(lower_bound)

    print(f'[~] Tame/Wild helds: {herd_size}, lower: {lower_bound}, upper: {upper_bound}, size: {upper_bound - lower_bound}')

    generator = get_next_triangular(upper, upper_idx, N, 1)
    while len(tame) != herd_size:
        (upper, upper_idx) = next(generator)
        if upper > upper_bound:
            print(f'\nFail fill Tame/Wild with N={N}')
            exit()
        tame.append(gmpy2.mpz(upper))
        wild.append(gmpy2.mpz(upper_idx))
        print(f'[~] Tame/Wild herds current: {len(tame)}', end = '\r')

    return (tame, wild)

################################################################################################
def check_consecutive_bits(number, N):
    if N == 0:
        return True
       
    count_zeros = 0
    count_ones = 0
   
    # Проходим по каждому биту числа
    while number > 0:
        # Проверяем текущий бит числа
        if number & 1 == 0:
            count_zeros += 1
            count_ones = 0
        else:
            count_ones += 1
            count_zeros = 0
       
        # Если подряд N одинаковых битов найдено, возвращаем True
        if count_zeros > N or count_ones > N:
            return False
       
        # Сдвигаем число на 1 вправо для проверки следующего бита
        number >>= 1
   
    # Если не нашли подряд N одинаковых битов
    return True

def closest_triangular_numbers(n):
    def triangular_number(i):
        return (i * (i + 1)) // 2

    left, right = 1, int((2 * n) ** 0.5) + 1

    while left <= right:
        mid = (left + right) // 2
        t_mid = triangular_number(mid)
        if t_mid == n:
            upper_i = mid + 1
            upper_t = triangular_number(upper_i)
            return ( (t_mid, mid), (upper_t, upper_i) )
        elif t_mid < n:
            left = mid + 1
        else:
            right = mid - 1

    lower_i = right
    lower_t = triangular_number(lower_i)
    upper_i = right + 1
    upper_t = triangular_number(upper_i)
    return ( (lower_t, lower_i), (upper_t, upper_i) )

def get_next_triangular(value, index, N, operation):
    while True:
        index += operation
        value += index * operation
        if check_consecutive_bits(value, N) and check_consecutive_bits(index, N):
            yield (value, index)


################################################################################################
def test(puzzle_complexity, compressed_pubkey, N):

    import time
    start_time = time.time()


    herd_size   = 2 ** (puzzle_complexity // 5)
    lower_bound = 2 ** (puzzle_complexity - 1)
    upper_bound = (2 ** puzzle_complexity) - 1

    tame_start_values, wild_start_values = gen_tame_wild(lower_bound, upper_bound, herd_size, N)

    hours, rem = divmod(time.time() - start_time, 3600)
    minutes, seconds = divmod(rem, 60)
    elapsed_str = f"{int(hours):02d}:{int(minutes):02d}:{int(seconds):02d}"
    print(f'\n[+] Tame and Wild herds initialized. {elapsed_str}')

    for x in tame_start_values:
        print(bin(x)[2:])
    for x in wild_start_values:
        print(bin(x)[2:])


if __name__ == '__main__':

    N = 4

    puzzle_complexity = 40
    compressed_pubkey = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4"
   
    #puzzle_complexity = 53
    #compressed_pubkey = "020faaf5f3afe58300a335874c80681cf66933e2a7aeb28387c0d28bb048bc6349"
   
    test(puzzle_complexity, compressed_pubkey, N)

import gmpy2

from twset.twset_b11 import gen_tame_wild
#from twset.twset_b12 import gen_tame_wild
#from twset.twset_b21 import gen_tame_wild
#from twset.twset_b22 import gen_tame_wild

N = gmpy2.mpz(6)

puzzle_complexity = 40
compressed_pubkey = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4"

#puzzle_complexity = 41
#compressed_pubkey = "03b357e68437da273dcf995a474a524439faad86fc9effc300183f714b0903468b"

#puzzle_complexity = 160
#compressed_pubkey = "02e0a8b039282faf6fe0fd769cfbc4b6b4cf8758ba68220eac420e32b91ddfa673"

#puzzle_complexity = 135
#compressed_pubkey = "02145d2611c823a396ef6712ce0f712f09b9b4f3135e3e0aa3230fb9b6d08d1e16"

#puzzle_complexity = 53
#compressed_pubkey = "020faaf5f3afe58300a335874c80681cf66933e2a7aeb28387c0d28bb048bc6349"

#puzzle_complexity = 20
#compressed_pubkey = "033c4a45cbd643ff97d77f41ea37e843648d50fd894b864b0d52febc62f6454f7c"

##########################################################################################

import time
import os
import sys
import random
from math import log2, sqrt, log

# Очистка экрана в зависимости от ОС
if os.name == 'nt':
    os.system('cls')
else:
    os.system('clear')
current_time = time.ctime()
sys.stdout.write("\033[?25l")  # Скрыть курсор
sys.stdout.write(f"\033[01;33m[+] Kangaroo: {current_time}\n")
sys.stdout.flush()

# Параметры эллиптической кривой secp256k1
modulus = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
curve_order = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)
generator_x = gmpy2.mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
generator_y = gmpy2.mpz(0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

base_point = (generator_x, generator_y)

def elliptic_curve_add(point1, point2):
    infinity = (0, 0)
    if point1 == infinity:
        return point2
    if point2 == infinity:
        return point1
   
    x1, y1 = point1
    x2, y2 = point2

    if x1 == x2:
        if y1 == y2:
            # Удвоение точки
            denominator = (y1 << 1) % modulus
            inv_denominator = gmpy2.invert(denominator, modulus)
            slope = (3 * x1 * x1 * inv_denominator) % modulus
        else:
            return infinity
    else:
        x_diff = (x2 - x1) % modulus
        inv_x_diff = gmpy2.invert(x_diff, modulus)
        slope = ((y2 - y1) * inv_x_diff) % modulus

    result_x = (slope * slope - x1 - x2) % modulus
    result_y = (slope * (x1 - result_x) - y1) % modulus
   
    return (result_x, result_y)

def scalar_multiply(scalar, point=base_point):
    result = (0, 0)
    current_point = point
    while scalar:
        if scalar & 1:
            result = elliptic_curve_add(result, current_point)
        current_point = elliptic_curve_add(current_point, current_point)
        scalar >>= 1
    return result

def x_to_y(x_coord, y_parity, prime=modulus):
    x_cubed = gmpy2.powmod(x_coord, 3, prime)
    x_squared = gmpy2.powmod(x_coord, 2, prime)
    y_squared = (x_cubed + 7) % prime
    y_coord = gmpy2.powmod(y_squared, (prime + 1) // 4, prime)
   
    if y_parity == 1:
        y_coord = (-y_coord) % prime
    return y_coord

def generate_power_steps(max_power):
    return [gmpy2.mpz(1 << power) for power in range(max_power)]

def handle_found_solution(private_key):
    hex_representation = "%064x" % abs(private_key)
    decimal_value = int(hex_representation, 16)
    print("\n\033[32m[+] PUZZLE SOLVED \033[0m")
    print(f"\033[32m[+] Private key (dec): {decimal_value} \033[0m")
    with open("KEYFOUNDKEYFOUND.txt", "a") as file:
        file.write(f"\n\nSOLVED {current_time}")
        file.write(f"\nPrivate Key (decimal): {decimal_value}")
        file.write(f"\nPrivate Key (hex): {hex_representation}")
        file.write(f"\n{'-' * 100}\n")
    return True

def kangaroo_search(precomputed_points, wild_start_point, dp_rarity, herd_size,
                   max_hop_power, upper_bound, lower_bound, power_steps):

    solution_found = False

    # Инициализация кенгуру
    start_time0 = time.time()

    start_time = time.time()
    tame_start_values, wild_start_values = gen_tame_wild(lower_bound, upper_bound, herd_size, N)
    hours, rem = divmod(time.time() - start_time, 3600)
    minutes, seconds = divmod(rem, 60)
    elapsed_str = f"{int(hours):02d}:{int(minutes):02d}:{int(seconds):02d}"
    print(f'\n[+] Tame and wild herds initialized. {elapsed_str}')

    start_time = time.time()
    tame_points = [scalar_multiply(value) for value in tame_start_values]
    hours, rem = divmod(time.time() - start_time, 3600)
    minutes, seconds = divmod(rem, 60)
    elapsed_str = f"{int(hours):02d}:{int(minutes):02d}:{int(seconds):02d}"
    print(f'[+] Tame points initialized. {elapsed_str}')

    start_time = time.time()
    wild_points = [elliptic_curve_add(wild_start_point, scalar_multiply(value)) for value in wild_start_values]
    hours, rem = divmod(time.time() - start_time, 3600)
    minutes, seconds = divmod(rem, 60)
    elapsed_str = f"{int(hours):02d}:{int(minutes):02d}:{int(seconds):02d}"
    print(f'[+] Wild points initialized. {elapsed_str}')
   
    start_time = time.time()
    tame_steps = [gmpy2.mpz(0) for _ in range(herd_size)]
    wild_steps = tame_steps.copy()
    hours, rem = divmod(time.time() - start_time, 3600)
    minutes, seconds = divmod(rem, 60)
    elapsed_str = f"{int(hours):02d}:{int(minutes):02d}:{int(seconds):02d}"
    print(f'[+] Tame and wild steps initialized. {elapsed_str}')
   
    hours, rem = divmod(time.time() - start_time0, 3600)
    minutes, seconds = divmod(rem, 60)
    elapsed_str = f"{int(hours):02d}:{int(minutes):02d}:{int(seconds):02d}"
    print(f'[+] Tame and wild points initialized. {elapsed_str}')
   
    total_hops = 0
    previous_hops_count = 0
    tame_distinguished_points = {}
    wild_distinguished_points = {}
    last_print_time = time.time()
    search_start_time = time.time()
   
    while True:
        # Обработка ручных кенгуру
        for idx in range(herd_size):
            total_hops += 1
            power_index = int(tame_points[idx][0] % max_hop_power)
            step_size = power_steps[power_index]
           
            if tame_points[idx][0] % dp_rarity == 0:
                x_coord = tame_points[idx][0]
                if x_coord in wild_distinguished_points:
                    solution = wild_distinguished_points[x_coord] - tame_start_values[idx]
                    solution_found = handle_found_solution(solution)
                    break
                tame_distinguished_points[x_coord] = tame_start_values[idx]
           
            tame_start_values[idx] += step_size
            tame_points[idx] = elliptic_curve_add(precomputed_points[power_index], tame_points[idx])
        if solution_found: break

        # Обработка диких кенгуру
        for idx in range(herd_size):
            total_hops += 1
            power_index = int(wild_points[idx][0] % max_hop_power)
            step_size = power_steps[power_index]
           
            if wild_points[idx][0] % dp_rarity == 0:
                x_coord = wild_points[idx][0]
                if x_coord in tame_distinguished_points:
                    solution = wild_start_values[idx] - tame_distinguished_points[x_coord]
                    solution_found = handle_found_solution(solution)
                    break
                wild_distinguished_points[x_coord] = wild_start_values[idx]
           
            wild_start_values[idx] += step_size
            wild_points[idx] = elliptic_curve_add(precomputed_points[power_index], wild_points[idx])
        if solution_found: break
       
        # Вывод статистики
        current_time = time.time()
        if current_time - last_print_time >= 5:
            elapsed_since_last = current_time - last_print_time
            hops_since_last = total_hops - previous_hops_count
            hops_per_sec = hops_since_last / elapsed_since_last if elapsed_since_last > 0 else 0
           
            total_elapsed = current_time - search_start_time
            hours, rem = divmod(total_elapsed, 3600)
            minutes, seconds = divmod(rem, 60)
            elapsed_str = f"{int(hours):02d}:{int(minutes):02d}:{int(seconds):02d}"
           
            last_print_time = current_time
            previous_hops_count = total_hops
           
            print(f'[+] [Hops: 2^{log2(total_hops):.2f} <-> {hops_per_sec:.0f} h/s] [{elapsed_str}]',
                  end='\r', flush=True)

    print()
    print(f'[+] Total hops: {total_hops}')
    hours, rem = divmod(time.time() - search_start_time, 3600)
    minutes, seconds = divmod(rem, 60)
    elapsed_str = f"{int(hours):02d}:{int(minutes):02d}:{int(seconds):02d}"
    print(f'[+] Search duration: {elapsed_str}')
    return solution_found

lower_bound = 2 ** (puzzle_complexity - 1)
upper_bound = (2 ** puzzle_complexity) - 1
dp_rarity = 1 << ((puzzle_complexity - 1) // 2 - 2) // 2 + 2

max_hop_power = round(log(2 ** puzzle_complexity) + 5)
herd_size = 2 ** (puzzle_complexity // 5)
power_steps = generate_power_steps(max_hop_power)

# Декодирование публичного ключа
if len(compressed_pubkey) == 66:
    x_coord = gmpy2.mpz(int(compressed_pubkey[2:66], 16))
    y_parity = int(compressed_pubkey[:2]) - 2
    y_coord = x_to_y(x_coord, y_parity)
else:
    print("[ERROR] Invalid public key format")
    sys.exit(1)

wild_start_point = (x_coord, y_coord)

# Предварительный расчет точек для прыжков
precomputed_points = [base_point]
for _ in range(max_hop_power - 1):
    precomputed_points.append(elliptic_curve_add(precomputed_points[-1], precomputed_points[-1]))
print(f'[+] Precomputed jump points ready: {max_hop_power}')

# Запуск поиска
search_start_time = time.time()
print(f"[+] Puzzle complexity: {puzzle_complexity}-bit")
print(f"[+] N: {N}-bit")
print(f"[+] Search range: 2^{puzzle_complexity-1} - 2^{puzzle_complexity}")
print(f"[+] Distinguished point rarity: 2^{int(log2(dp_rarity))}")
print(f"[+] Distinguished point rarity: {dp_rarity}")
expected_hops = 2.13 * sqrt(2 ** puzzle_complexity)
print(f"[+] Expected hops: 2^{log2(expected_hops):.2f} ({int(expected_hops)})")

search_start_time_begin = kangaroo_search(
    precomputed_points,
    wild_start_point,
    dp_rarity,
    herd_size,
    max_hop_power,
    upper_bound,
    lower_bound,
    power_steps
)

hours, rem = divmod(time.time() - search_start_time, 3600)
minutes, seconds = divmod(rem, 60)
elapsed_str = f"{int(hours):02d}:{int(minutes):02d}:{int(seconds):02d}"
print(f"[+] Total execution time: {elapsed_str}")