org.apache.commons.math3.primes
Class PollardRho

java.lang.Object
  extended by org.apache.commons.math3.primes.PollardRho

 class PollardRho
extends Object

Implementation of the Pollard's rho factorization algorithm.

Since:
3.2
Version:
$Id: PollardRho.java 1462702 2013-03-30 04:45:52Z psteitz $

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

PollardRho

private PollardRho()
Hide utility class.

Method Detail

primeFactors

public static List<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:

Parameters:
a - first number, must be ≥ 0
b - second number, must be ≥ 0
Returns:
gcd(a,b)


Copyright (c) 2003-2013 Apache Software Foundation