class PollardRho
extends java.lang.Object
Modifier | Constructor and Description |
---|---|
private |
PollardRho()
Hide utility class.
|
Modifier and Type | Method and 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.
|
public static java.util.List<java.lang.Integer> primeFactors(int n)
n
- number to factors, must be > 0static int rhoBrent(int n)
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.
n
- number to factor, must be semi-prime.static int gcdPositive(int a, int b)
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:gcd(x, x)
, gcd(0, x)
and gcd(x, 0)
is the value of x
.gcd(0, 0)
is the only one which returns 0
.a
- first number, must be ≥ 0b
- second number, must be ≥ 0Copyright (c) 2003-2016 Apache Software Foundation