rsa

#!/usr/bin/python3

import sys
from typing import Tuple


def calculate_gcd(a: int, b: int) -> int:
    """Calculate the greatest common divisor of two integers."""
    while b:
        a, b = b, a % b
    return a


def pollards_rho_factorization(n: int) -> Tuple[int, int]:
    """
    Apply Pollard's rho algorithm to factorize a given integer.

    Args:
        n (int): The integer to be factorized.

    Returns:
        Tuple[int, int]: A tuple containing two factors of the input integer.
    """
    if n % 2 == 0:
        return 2, n // 2

    x, y, d = 2, 2, 1
    f = lambda x: (x**2 + 1) % n

    while d == 1:
        x = f(x)
        y = f(f(y))
        d = calculate_gcd(abs(x - y), n)

    return d, n // d


def factorize_number(number: int) -> Tuple[int, int]:
    """
    Factorize a given integer into two smaller integers.

    Args:
        number (int): The integer to be factorized.

    Returns:
        Tuple[int, int]: A tuple containing two factors of the input integer.
    """
    if number <= 1:
        return number, 1
    else:
        return pollards_rho_factorization(number)


def main(filename: str) -> None:
    """
    Main function to read numbers from a file and print their factorizations.

    Parameters:
        filename (str): The name of the file containing natural
        numbers to factor.
    """
    try:
        with open(filename, "r") as file:
            for line in file:
                current_number = int(line.strip())
                factor1, factor2 = factorize_number(current_number)
                print(f"{current_number}={factor1}*{factor2}")
    except FileNotFoundError:
        print(f"Error: File '{filename}' not found.")
    except ValueError:
        print(
            "Error: Invalid content in the file. "
            + "Please ensure all lines contain valid natural "
            + "numbers greater than 1."
        )


if __name__ == "__main__":
    if len(sys.argv) != 2:
        print("Usage: factors file")
        sys.exit(1)

    input_filename = sys.argv[1]
    main(input_filename)