|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.apache.commons.math3.primes.PollardRho
class PollardRho
Implementation of the Pollard's rho factorization algorithm.
Constructor Summary | |
---|---|
private |
PollardRho()
Hide utility class. |
Method Summary | |
---|---|
(package private) static int |
gcdPositive(int a,
int b)
Gcd between two positive numbers. |
static List<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 |
---|
private PollardRho()
Method Detail |
---|
public static List<Integer> primeFactors(int n)
n
- number to factors, must be > 0
static 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 ≥ 0
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |