import time
import logging

# Configure the logger
logging.basicConfig(
    filename='pollard_rho.log',  # Log file name
    level=logging.INFO,          # Logging level (INFO, DEBUG, WARNING, ERROR, CRITICAL)
    format='%(asctime)s - %(message)s',  # Log format
    filemode='w'  # 'w' to overwrite the file, 'a' to append to the file
)

def gcd(a, b):
    r0, r1 = a, b
    x0, y0, x1, y1 = 1, 0, 0, 1
    while r1 != 0:
        q = r0 // r1
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
        r1, r0 = r0 % r1, r1
        if r1 > r0 >> 1:
            r1 = r0 - r1
            x1 = x0 - x1
            y1 = y0 - y1
    return x0, y0, r0

def v(a, b):
    """Returns the absolutely smallest residue of a modulo b"""
    r1 = a % b
    r2 = r1 - b
    return r1 if abs(r1) < abs(r2) else r2

def order(a, p):
    """Returns the order of a modulo p"""
    i, x = 1, 0
    while x != 1:
        x, i = pow(a, i, p), i + 1
    return i - 1

def f(c, a, b, p, log):
    if c < 0: 
        log[0] += 1
        return v(a * c, p)
    else: 
        log[1] += 1
        return v(b * c, p)

def solve(a, b, m):
    d = gcd(a, m)[2]
    a1, b1, m1 = a // d, b // d, m // d
    x0 = b1 * gcd(a1, m1)[0]
    return x0 % m

def pollard_rho(a, b, p, ord=None):
    u, v = 1, 1
    d = c = pow(a, u, p) * pow(b, v, p) % p
    log_c, log_d = [1, 1], [1, 1]
    
    i = 0
    while True:
        i += 1
        c = f(c, a, b, p, log_c)
        d = f(f(d, a, b, p, log_d), a, b, p, log_d)
        
        # Log every 10 million iterations
        if i % 10_000_000 == 0: 
            print(f"Iteration {i} | c = {c} | {log_c[0]}+{log_c[1]}x | d = {d} | {log_d[0]}+{log_d[1]}x")
            logging.info(f"Iteration {i} | c = {c} | {log_c[0]}+{log_c[1]}x | d = {d} | {log_d[0]}+{log_d[1]}x")
        
        if c == d: 
            logging.info(f"Match found at iteration {i}: c = {c}, d = {d}")
            break
    
    if ord is None:
        ord = order(a, p)
        logging.info(f"Order of element a modulo p: {ord}")
    
    # Log the final comparison
    logging.info(f"Comparison: {log_c[0]}+{log_c[1]}x = {log_d[0]}+{log_d[1]}x (mod {ord})")
    logging.info(f"Simplified comparison: {log_c[1]-log_d[1]}x = {log_d[0]-log_c[0]} (mod {ord})")
    
    return solve(log_c[1]-log_d[1], log_d[0]-log_c[0], ord)

if __name__ == "__main__":
    # Example usage
    logging.info("Starting Pollard's Rho algorithm")
    # result = pollard_rho(2, 7, 137)
    result = pollard_rho(2, 11, 50091285122438801159, ord=25045642561219400579)
    logging.info(f"Result: x = {result}")
    print(f"Result: x = {result}")