An implementation of Pollard Rho and Trial Division factoring algorithms

factoring.py

import math
import time

FACTOR = [10972771937, 1690899676867]

def f(x):
    return x**2 + 1

def pollard_rho(N):
    xn = 2
    x2n = 2
    #print("xn: {}, x2n: {}".format(xn, x2n))
    d = 1
    while d == 1:
        xn = f(xn) % N
        x2n = f(f(x2n)) % N
        #print("xn: {}, x2n: {}".format(xn, x2n))
        abs_val = abs(xn - x2n)
        d = math.gcd(abs_val, N)
    if d == N:
        return False
    else:
        return d, N//d
      
def trial_division(N):
  for d in range(2, N):
    if N % d == 0:
      return d, N // d


for factor in FACTOR:
  print("\n\nFACTORING {}".format(factor))
  start_time = time.time()
  print(pollard_rho(factor))
  print("Pollard Rho Took: {}".format(time.time() - start_time))
  start_time = time.time()
  print(trial_division(factor))
  print("Trial Division Took: {}".format(time.time() - start_time))