Repository: sympy/sympy
File: sympy/ntheory/factor_.py (Python)

Code before:

    >>> from sympy import pollard_rho
    >>> n=16843009
    >>> F=lambda x:(2048*pow(x,2,n) + 32767) % n
    >>> pollard_rho(n, F=F)
    257

    Use the default setting with a bad value of ``a`` and no retries:

    >>> pollard_rho(n, a=n-2, retries=0)

    If retries is > 0 then perhaps the problem will correct itself when
    new values are generated for a:

    >>> pollard_rho(n, a=n-2, retries=1)
    257

    References
    ==========

    .. [1] Richard Crandall & Carl Pomerance (2005), "Prime Numbers:
           A Computational Perspective", Springer, 2nd edition, 229-231

    """
    n = int(n)
    if n < 5:
        raise ValueError('pollard_rho should receive n > 4')
    randint = _randint(seed + retries)
    V = s
    for i in range(retries + 1):
        U = V
        if not F:
            F = lambda x: (pow(x, 2, n) + a) % n
        j = 0
        while 1:
            if max_steps and (j > max_steps):
                break
            j += 1
            U = F(U)
            V = F(F(V))  # V is 2x further along than U
            g = gcd(U - V, n)
            if g == 1:
                continue
            if g == n:
                break
            return int(g)
        V = randint(0, n - 1)
        a = randint(1, n - 3)  # for x**2 + a, a%n should not be 0 or -2
        F = None
    return None


Review comment (performance):
Coming here from the user-facing documentation: It's unclear to me what "_the_ prime factor of `n`" means. Source-diving a little bit, it looks like the cache holds only one prime factor per input number; to get the full factorization of the input number you'd have to call `sympy.factor_cache.get` in a loop... except that that's what `sympy.ntheory.primefactors(n)` already does for you, so the user should never actually have to interact with `sympy.factor_cache` except perhaps to do

    sympy.factor_cache = sympy.FactorCache(maxsize=100000)

at the start of their program. Is that basically correct?

And if so, this docstring should be updated to give the user some of this information. Simply replacing "Return the prime factor of `n`" with "Return one prime factor of `n`" or "Return the largest prime factor of `n` previously memoized by the cache" would be a big improvement.

Code after:
            raise KeyError(f"{n} does not exist.")
        del self._cache[n]

    def __iter__(self):
        return self._cache.__iter__()

    def cache_clear(self) -> None:
        """ Clear the cache """
        self._cache = OrderedDict()

    @property
    def maxsize(self) -> int | None:
        """ Returns the maximum cache size; if ``None``, it is unlimited. """
        return self._maxsize

    @maxsize.setter
    def maxsize(self, value: int | None) -> None:
        if value is not None and value <= 0:
            raise ValueError("maxsize must be None or a non-negative integer.")
        self._maxsize = value
        if value is not None:
            while len(self._cache) > value:
                self._cache.popitem(False)

    def get(self, n: int, default=None):
        """ Return the prime factor of ``n``.
        If it does not exist in the cache, return the value of ``default``.
        """
        if n <= sieve._list[-1]:
            if sieve._list[bisect_left(sieve._list, n)] == n:
                return n
        if n in self._cache:
            self._cache.move_to_end(n)
            return self._cache[n]
        if factors := self.get_external(n):
            self.add(n, factors)
            return self._cache[n]
        return default

    def add(self, n: int, factors: list[int]) -> None:
        for p in sorted(factors, reverse=True):
            self[n] = p
            n, _ = remove(n, p)

    def get_external(self, n: int) -> list[int] | None:
        return None


factor_cache = FactorCache(maxsize=1000)