Package org.apache.commons.math3.primes
Class PollardRho
java.lang.Object
org.apache.commons.math3.primes.PollardRho
Implementation of the Pollard's rho factorization algorithm.
- Since:
- 3.2
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) static int
gcdPositive
(int a, int b) Gcd between two positive numbers.primeFactors
(int n) Factorization using Pollard's rho algorithm.(package private) static int
rhoBrent
(int n) Implementation of the Pollard's rho factorization algorithm.
-
Constructor Details
-
PollardRho
private PollardRho()Hide utility class.
-
-
Method Details
-
primeFactors
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)
andgcd(x, 0)
is the value ofx
. - The invocation
gcd(0, 0)
is the only one which returns0
.
- Parameters:
a
- first number, must be ≥ 0b
- second number, must be ≥ 0- Returns:
- gcd(a,b)
- The result of
-