# Safa Bacanli
# 10/23/2018
# Solution to Fall 2018 CIS 3362 Homework #5 Question #9

import math
import time


def gcd( a, b ):
    while a % b != 0:
        a, b = b, a % b
    return b


#in wikipedia	
def rho( n ):
    x_fixed = 2
    cycle_size = 2
    x = 2
    factor = 1

    while factor == 1:
        count = 1
        while count <= cycle_size and factor <= 1:
            x = (x * x + 1) % n
            factor = gcd(x - x_fixed, n)
            count += 1
        cycle_size *= 2
        x_fixed = x

    print(str(int(factor)) + " " + str(int((n / factor))))

#This is the algorithm in Arup Guha's notes
def rho2( n: int ):
    a = 2
    b = 2
    done = False
    while done == False:
        a = (a * a + 1) % n
        b = (b * b + 1) % n
        b = (b * b + 1) % n
        d = gcd(abs(a - b), n)
        if 1 < d and d < n:
            number2 = n // d
            print(str(d) + " " + str(number2))
            done = True
        if d == n:
            print("failed")
            done = True


# https://stackoverflow.com/questions/20464561/fermat-factorisation-with-python
def isqrt( n ):
    x = n
    y = (x + n // x) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x


# https://stackoverflow.com/questions/20464561/fermat-factorisation-with-python
def fermat( n ):
    a = isqrt(n)  # int(ceil(n**0.5))
    b2 = a * a - n
    b = isqrt(n)  # int(b2**0.5)
    count = 0
    while b * b != b2:
        a = a + 1
        b2 = a * a - n
        b = isqrt(b2)  # int(b2**0.5)
        count += 1
    p = a + b
    q = a - b
    print(q, " ", p)


# https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
# A function to print all prime factors of  
# a given number n 
def primeFactors( n ):
    # Print the number of two's that divide n
    while n % 2 == 0:
        print("2 ")
        n = n / 2

    # n must be odd at this point 
    # so a skip of 2 ( i = i + 2) can be used 
    for i in range(3, int(math.sqrt(n)) + 1, 2):

        # while i divides n , print i ad divide n 
        if n % i == 0:
            number2 = n / i
            print(str(i) + " " + str(number2))
            break


arr = [441075437627829133, 733561193479131791, 611217877192686991, 1442059257386438303, 3008502085141882717]
for el in arr:
    
    print(str(el)+"\n")
    start_time = time.clock()
    primeFactors(el)
    end_time = time.clock()
    difference = (end_time - start_time)
    print(difference, "seconds for factoring")

    start_time = time.clock()
    fermat(el)
    end_time = time.clock()
    difference = (end_time - start_time)
    print(difference, "seconds for fermat factoring")
    
    start_time = time.clock()
    rho(el)
    end_time = time.clock()
    difference = (end_time - start_time)
    print(difference, "seconds for rho factoring")
    
    start_time = time.clock()
    rho2(el)
    end_time = time.clock()
    difference = (end_time - start_time)
    print(difference, "seconds for rho2 factoring")