| Access | Constructor and Description |
|---|---|
| private |
| Modifier and Type | Method and Description |
|---|---|
| pack-priv static int | Returns: gcd(a,b)first number, must be ≥ 0 a, int second number, must be ≥ 0 b)Gcd between two positive numbers. |
| public static List | Returns: the list of prime factors of n.number to factors, must be > 0 n)Factorization using Pollard's rho algorithm. |
| pack-priv static int | Returns: a prime factor of n.number to factor, must be semi-prime. n)Implementation of the Pollard's rho factorization algorithm. |
| PollardRho | back to summary |
|---|---|
| private PollardRho() Hide utility class. | |
| gcdPositive | back to summary |
|---|---|
| pack-priv 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:
| |
| primeFactors | back to summary |
|---|---|
| public static List Factorization using Pollard's rho algorithm. | |
| rhoBrent | back to summary |
|---|---|
| pack-priv static int rhoBrent(final 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.
| |