89 lines
2.6 KiB
Python
89 lines
2.6 KiB
Python
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}") |