Class PollardRho


  • class PollardRho
    extends java.lang.Object
    Implementation of the Pollard's rho factorization algorithm.
    Since:
    3.2
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private PollardRho()
      Hide utility class.
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) static int gcdPositive​(int a, int b)
      Gcd between two positive numbers.
      static java.util.List<java.lang.Integer> primeFactors​(int n)
      Factorization using Pollard's rho algorithm.
      (package private) static int rhoBrent​(int n)
      Implementation of the Pollard's rho factorization algorithm.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • PollardRho

        private PollardRho()
        Hide utility class.
    • Method Detail

      • primeFactors

        public static java.util.List<java.lang.Integer> primeFactors​(int n)
        Factorization using Pollard's rho algorithm.
        Parameters:
        n - number to factors, must be > 0
        Returns:
        the list of prime factors of n.
      • rhoBrent

        static int rhoBrent​(int n)
        Implementation of the Pollard's rho factorization algorithm.

        This implementation follows the paper "An improved Monte Carlo factorization algorithm" by Richard P. Brent. This avoids the triple computation of f(x) typically found in Pollard's rho implementations. It also batches several gcd computation into 1.

        The backtracking is not implemented as we deal only with semi-primes.

        Parameters:
        n - number to factor, must be semi-prime.
        Returns:
        a prime factor of n.
      • gcdPositive

        static int gcdPositive​(int a,
                               int b)
        Gcd between two positive numbers.

        Gets the greatest common divisor of two numbers, using the "binary gcd" method, which avoids division and modulo operations. See Knuth 4.5.2 algorithm B. This algorithm is due to Josef Stein (1961).

        Special cases:
        • The result of gcd(x, x), gcd(0, x) and gcd(x, 0) is the value of x.
        • The invocation gcd(0, 0) is the only one which returns 0.
        Parameters:
        a - first number, must be ≥ 0
        b - second number, must be ≥ 0
        Returns:
        gcd(a,b)