use pollard s rho algorithm to return a nontrivial factor of num the returned factor may be composite and require further factorization if the algorithm will return none if it fails to find a factor within the specified number of attempts or within the specified number of steps if num is prime this algorithm is guaranteed to return none https en wikipedia orgwikipollard27srhoalgorithm pollardrho18446744073709551617 274177 pollardrho97546105601219326301 9876543191 pollardrho100 2 pollardrho17 pollardrho173 17 pollardrho173 attempts1 pollardrho357 21 pollardrho1 traceback most recent call last valueerror the input value cannot be less than 2 a value less than 2 can cause an infinite loop in the algorithm because of the relationship between ffx and fx this algorithm struggles to find factors that are divisible by two as a workaround we specifically check for two and even inputs see https math stackexchange coma2856214165820 pollard s rho algorithm requires a function that returns pseudorandom values between 0 x num it doesn t need to be random in the sense that the output value is cryptographically secure or difficult to calculate it only needs to be random in the sense that all output values should be equally likely to appear for this reason pollard suggested using fx x2 1 num however the success of pollard s algorithm isn t guaranteed and is determined in part by the initial seed and the chosen random function to make retries easier we will instead use fx x2 c num where c is a value that we can modify between each attempt returns a pseudorandom value modulo modulus based on the input value and attemptspecific step size randfn0 0 0 traceback most recent call last zerodivisionerror integer division or modulo by zero randfn1 2 3 0 randfn0 10 7 3 randfn1234 1 17 16 these track the position within the cycle detection logic at each iteration the tortoise moves one step and the hare moves two at some point both the tortoise and the hare will enter a cycle whose length p is a divisor of num once in that cycle at some point the tortoise and hare will end up on the same value modulo p we can detect when this happens because the position difference between the tortoise and the hare will share a common divisor with num no common divisor yet just keep searching we found a common divisor unfortunately the divisor is num itself and is useless the divisor is a nontrivial factor of num if we made it here then this attempt failed we need to pick a new starting seed for the tortoise and hare in addition to a new step value for the random function to keep this example implementation deterministic the new values will be generated based on currently available values instead of using something like random randint we can use the hare s position as the new seed this is actually what richard brent s the optimized variant does the new step value for the random function can just be incremented at first the results will be similar to what the old function would have produced but the value will quickly diverge after a bit we haven t found a divisor within the requested number of attempts we were unlucky or num itself is actually prime use pollard s rho algorithm to return a nontrivial factor of num the returned factor may be composite and require further factorization if the algorithm will return none if it fails to find a factor within the specified number of attempts or within the specified number of steps if num is prime this algorithm is guaranteed to return none https en wikipedia org wiki pollard 27s_rho_algorithm pollard_rho 18446744073709551617 274177 pollard_rho 97546105601219326301 9876543191 pollard_rho 100 2 pollard_rho 17 pollard_rho 17 3 17 pollard_rho 17 3 attempts 1 pollard_rho 3 5 7 21 pollard_rho 1 traceback most recent call last valueerror the input value cannot be less than 2 a value less than 2 can cause an infinite loop in the algorithm because of the relationship between f f x and f x this algorithm struggles to find factors that are divisible by two as a workaround we specifically check for two and even inputs see https math stackexchange com a 2856214 165820 pollard s rho algorithm requires a function that returns pseudorandom values between 0 x num it doesn t need to be random in the sense that the output value is cryptographically secure or difficult to calculate it only needs to be random in the sense that all output values should be equally likely to appear for this reason pollard suggested using f x x 2 1 num however the success of pollard s algorithm isn t guaranteed and is determined in part by the initial seed and the chosen random function to make retries easier we will instead use f x x 2 c num where c is a value that we can modify between each attempt returns a pseudorandom value modulo modulus based on the input value and attempt specific step size rand_fn 0 0 0 traceback most recent call last zerodivisionerror integer division or modulo by zero rand_fn 1 2 3 0 rand_fn 0 10 7 3 rand_fn 1234 1 17 16 these track the position within the cycle detection logic at each iteration the tortoise moves one step and the hare moves two at some point both the tortoise and the hare will enter a cycle whose length p is a divisor of num once in that cycle at some point the tortoise and hare will end up on the same value modulo p we can detect when this happens because the position difference between the tortoise and the hare will share a common divisor with num no common divisor yet just keep searching we found a common divisor unfortunately the divisor is num itself and is useless the divisor is a nontrivial factor of num if we made it here then this attempt failed we need to pick a new starting seed for the tortoise and hare in addition to a new step value for the random function to keep this example implementation deterministic the new values will be generated based on currently available values instead of using something like random randint we can use the hare s position as the new seed this is actually what richard brent s the optimized variant does the new step value for the random function can just be incremented at first the results will be similar to what the old function would have produced but the value will quickly diverge after a bit we haven t found a divisor within the requested number of attempts we were unlucky or num itself is actually prime
from __future__ import annotations

from math import gcd


def pollard_rho(
    num: int,
    seed: int = 2,
    step: int = 1,
    attempts: int = 3,
) -> int | None:
    
    
    if num < 2:
        raise ValueError("The input value cannot be less than 2")

    
    
    
    
    if num > 2 and num % 2 == 0:
        return 2

    
    
    
    
    
    
    
    
    
    
    def rand_fn(value: int, step: int, modulus: int) -> int:
        
        return (pow(value, 2) + step) % modulus

    for _ in range(attempts):
        
        tortoise = seed
        hare = seed

        while True:
            
            tortoise = rand_fn(tortoise, step, num)
            hare = rand_fn(hare, step, num)
            hare = rand_fn(hare, step, num)

            
            
            
            
            
            divisor = gcd(hare - tortoise, num)

            if divisor == 1:
                
                continue
            else:
                
                if divisor == num:
                    
                    break
                else:
                    
                    return divisor

        
        
        
        
        
        

        
        
        seed = hare

        
        
        
        step += 1

    
    
    return None


if __name__ == "__main__":
    import argparse

    parser = argparse.ArgumentParser()
    parser.add_argument(
        "num",
        type=int,
        help="The value to find a divisor of",
    )
    parser.add_argument(
        "--attempts",
        type=int,
        default=3,
        help="The number of attempts before giving up",
    )
    args = parser.parse_args()

    divisor = pollard_rho(args.num, attempts=args.attempts)
    if divisor is None:
        print(f"{args.num} is probably prime")
    else:
        quotient = args.num // divisor
        print(f"{args.num} = {divisor} * {quotient}")