# rho.py
# find a prime factor of a composite using Pollard's Rho algorithm 

'''
> python rho.py
n=? 111111111111111111111111111111113
One divisor for 111111111111111111111111111111113 = 1867
in 1.60 secs

> python rho.py
n=? 5166523324060302275610181
One divisor for 5166523324060302275610181 = 141325637
in 0.07 secs

> python rho.py
n=? 280846283204599997
Retrying
One divisor for 280846283204599997 = 265371653
in 0.09 secs

  https://www.numberempire.com/numberfactorizer.php
'''

import random, math, time
from millerRabin import *


def rho(n):
  if (n <= 1):
    return n
  if (n % 2 == 0):
    return 2
  # initialize random numbers in [2,n)
  x = random.randint(2, n-1)
  y = x
  # f(x) = (x^2 + c) mod n
  c = random.randint(1, n)
  d = 1
  # loop until the prime factor isn't obtained.
  # If n is prime, return n 
  while (d == 1):
    # slow move
    x = (modPow(x,2,n) + c+n)%n
    # fast move
    y = (modPow(y,2,n) + c+n)%n
    y = (modPow(y,2,n) + c+n)%n
    d = math.gcd(abs(x-y), n)
    if (d == n):  
      # detected a cycle with this x and c
      print("Retrying")
      return rho(n)
  # this means 1 < d < n, so found a prime
  return d

if __name__ == "__main__":
  n = int(input("n=? "))
  start = time.time()
  print("One divisor for", n, "=", rho(n))
  print(f"in {time.time()-start:.2f} secs")