rsa

#!/usr/bin/env python3

from sys import argv, exit
from math import gcd
from random import randint
from time import time


def read_test_file(file_name):
    """Function to read number from file: one number per file"""

    with open(file_name, "r", encoding="utf-8") as file:
        lines = file.readlines()

    number_to_factor = []

    for line in lines:
        # Check if the number has 100 or more digits
        n = int(line.strip())
        if n >= 10**99:
            factors = pollard_rho(n)
            print("{}={}*{}".format(n, factors[0], factors[1]))
        else:
            find_numbers(n)

    return number_to_factor


def find_numbers(n):
    """Function to find factors of current number"""

    for i in range(1, n):
        if n % i == 0:
            print("{}={}*{}".format(n, (n // i), i))
            break


def pollard_rho(n):
    """Function to factor a number using the Pollard Rho algorithm"""

    start_time = time()

    x = randint(0, n - 1)
    y = x
    c = randint(1, n - 1)
    d = 1

    while d == 1:

        if time() - start_time > 4:
            exit(100)

        x = (x*x + c) % n
        y = (y*y + c) % n
        y = (y*y + c) % n
        d = gcd(abs(x - y), n)

    if d == n:
        return pollard_rho(n)

    return (d, n // d)


def factors(ls):
    """Function to iterate between numbers in file"""

    for i in ls:
        find_numbers(i)


if len(argv) == 2:
    factors(read_test_file(argv[1]))