TheAlgorithms-Python
148 строк · 5.5 Кб
1from __future__ import annotations2
3from math import gcd4
5
6def pollard_rho(7num: int,8seed: int = 2,9step: int = 1,10attempts: int = 3,11) -> int | None:12"""13Use Pollard's Rho algorithm to return a nontrivial factor of ``num``.
14The returned factor may be composite and require further factorization.
15If the algorithm will return None if it fails to find a factor within
16the specified number of attempts or within the specified number of steps.
17If ``num`` is prime, this algorithm is guaranteed to return None.
18https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
19
20>>> pollard_rho(18446744073709551617)
21274177
22>>> pollard_rho(97546105601219326301)
239876543191
24>>> pollard_rho(100)
252
26>>> pollard_rho(17)
27>>> pollard_rho(17**3)
2817
29>>> pollard_rho(17**3, attempts=1)
30>>> pollard_rho(3*5*7)
3121
32>>> pollard_rho(1)
33Traceback (most recent call last):
34...
35ValueError: The input value cannot be less than 2
36"""
37# A value less than 2 can cause an infinite loop in the algorithm.38if num < 2:39raise ValueError("The input value cannot be less than 2")40
41# Because of the relationship between ``f(f(x))`` and ``f(x)``, this42# algorithm struggles to find factors that are divisible by two.43# As a workaround, we specifically check for two and even inputs.44# See: https://math.stackexchange.com/a/2856214/16582045if num > 2 and num % 2 == 0:46return 247
48# Pollard's Rho algorithm requires a function that returns pseudorandom49# values between 0 <= X < ``num``. It doesn't need to be random in the50# sense that the output value is cryptographically secure or difficult51# to calculate, it only needs to be random in the sense that all output52# values should be equally likely to appear.53# For this reason, Pollard suggested using ``f(x) = (x**2 - 1) % num``54# However, the success of Pollard's algorithm isn't guaranteed and is55# determined in part by the initial seed and the chosen random function.56# To make retries easier, we will instead use ``f(x) = (x**2 + C) % num``57# where ``C`` is a value that we can modify between each attempt.58def rand_fn(value: int, step: int, modulus: int) -> int:59"""60Returns a pseudorandom value modulo ``modulus`` based on the
61input ``value`` and attempt-specific ``step`` size.
62
63>>> rand_fn(0, 0, 0)
64Traceback (most recent call last):
65...
66ZeroDivisionError: integer division or modulo by zero
67>>> rand_fn(1, 2, 3)
680
69>>> rand_fn(0, 10, 7)
703
71>>> rand_fn(1234, 1, 17)
7216
73"""
74return (pow(value, 2) + step) % modulus75
76for _ in range(attempts):77# These track the position within the cycle detection logic.78tortoise = seed79hare = seed80
81while True:82# At each iteration, the tortoise moves one step and the hare moves two.83tortoise = rand_fn(tortoise, step, num)84hare = rand_fn(hare, step, num)85hare = rand_fn(hare, step, num)86
87# At some point both the tortoise and the hare will enter a cycle whose88# length ``p`` is a divisor of ``num``. Once in that cycle, at some point89# the tortoise and hare will end up on the same value modulo ``p``.90# We can detect when this happens because the position difference between91# the tortoise and the hare will share a common divisor with ``num``.92divisor = gcd(hare - tortoise, num)93
94if divisor == 1:95# No common divisor yet, just keep searching.96continue97# We found a common divisor!98elif divisor == num:99# Unfortunately, the divisor is ``num`` itself and is useless.100break101else:102# The divisor is a nontrivial factor of ``num``!103return divisor104
105# If we made it here, then this attempt failed.106# We need to pick a new starting seed for the tortoise and hare107# in addition to a new step value for the random function.108# To keep this example implementation deterministic, the109# new values will be generated based on currently available110# values instead of using something like ``random.randint``.111
112# We can use the hare's position as the new seed.113# This is actually what Richard Brent's the "optimized" variant does.114seed = hare115
116# The new step value for the random function can just be incremented.117# At first the results will be similar to what the old function would118# have produced, but the value will quickly diverge after a bit.119step += 1120
121# We haven't found a divisor within the requested number of attempts.122# We were unlucky or ``num`` itself is actually prime.123return None124
125
126if __name__ == "__main__":127import argparse128
129parser = argparse.ArgumentParser()130parser.add_argument(131"num",132type=int,133help="The value to find a divisor of",134)135parser.add_argument(136"--attempts",137type=int,138default=3,139help="The number of attempts before giving up",140)141args = parser.parse_args()142
143divisor = pollard_rho(args.num, attempts=args.attempts)144if divisor is None:145print(f"{args.num} is probably prime")146else:147quotient = args.num // divisor148print(f"{args.num} = {divisor} * {quotient}")149