maths.pollard_rho

Attributes

parser

Functions

pollard_rho(→ int | None)

Use Pollard's Rho algorithm to return a nontrivial factor of num.

Module Contents

maths.pollard_rho.pollard_rho(num: int, seed: int = 2, step: int = 1, attempts: int = 3) → int | None

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

maths.pollard_rho.parser