from ecdsa import SigningKey, SECP256k1
import ecdsa

# Define Puzzle #135 x-coordinate
p = 9210836494447108270027136741376870869791784014198948301625976867708124077590

# Define private key search range
k_lower = 21778071482940061661655974875633165533184 # + 10**26 
k_upper = 43556142965880123323311949751266331066367 # - 10**26

# Define a threshold to check for x-values near p
threshold = 10**76  # Adjust based on how "near" to p we want

def private_key_to_public_x(private_key):
    """Computes the x-coordinate of the public key from a given private key."""
    sk = SigningKey.from_secret_exponent(private_key, curve=SECP256k1)
    vk = sk.verifying_key
    x_coord = int.from_bytes(vk.to_string()[:32], 'big')  # Extract x-coordinate
    return x_coord

# Reduce step size to scan more precisely
step_size = int(1e35)  # Smaller step size for finer detail

print("Scanning for private keys that generate x-values close to p...")

matches = []

for k in range(k_lower, k_upper, step_size):
    x_value = private_key_to_public_x(k)
   
    if abs(p - x_value) < threshold:
        matches.append((k, x_value))

# Sort matches by x_value
matches.sort(key=lambda item: item[1])

# Print sorted results
for k, x in matches:
    print(f"Potential match: Private Key = {k}, x = {x}")

print("Scan complete.")
print(f"Found {len(matches)} potential matches.")

# Save sorted results to a file
with open("possible_matches.txt", "w") as f:
    for k, x in matches:
        f.write(f"Private Key: {k}, x: {x}\n")