org.apache.commons.math3.primes
Class SmallPrimes

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

 class SmallPrimes
extends Object

Utility methods to work on primes within the int range.

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

Field Summary
static int[] PRIMES
          The first 512 prime numbers.
static int PRIMES_LAST
          The last number in PRIMES.
 
Constructor Summary
private SmallPrimes()
          Hide utility class.
 
Method Summary
static int boundedTrialDivision(int n, int maxFactor, List<Integer> factors)
          Extract factors in the range PRIME_LAST+2 to maxFactors.
static boolean millerRabinPrimeTest(int n)
          Miller-Rabin probabilistic primality test for int type, used in such a way that a result is always guaranteed.
static int smallTrialDivision(int n, List<Integer> factors)
          Extract small factors.
static List<Integer> trialDivision(int n)
          Factorization by trial division.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

PRIMES

public static final int[] PRIMES
The first 512 prime numbers.

It contains all primes smaller or equal to the cubic square of Integer.MAX_VALUE. As a result, int numbers which are not reduced by those primes are guaranteed to be either prime or semi prime.


PRIMES_LAST

public static final int PRIMES_LAST
The last number in PRIMES.

Constructor Detail

SmallPrimes

private SmallPrimes()
Hide utility class.

Method Detail

smallTrialDivision

public static int smallTrialDivision(int n,
                                     List<Integer> factors)
Extract small factors.

Parameters:
n - the number to factor, must be > 0.
factors - the list where to add the factors.
Returns:
the part of n which remains to be factored, it is either a prime or a semi-prime

boundedTrialDivision

public static int boundedTrialDivision(int n,
                                       int maxFactor,
                                       List<Integer> factors)
Extract factors in the range PRIME_LAST+2 to maxFactors.

Parameters:
n - the number to factorize, must be >= PRIME_LAST+2 and must not contain any factor below PRIME_LAST+2
maxFactor - the upper bound of trial division: if it is reached, the method gives up and returns n.
factors - the list where to add the factors.
Returns:
n or 1 if factorization is completed.

trialDivision

public static List<Integer> trialDivision(int n)
Factorization by trial division.

Parameters:
n - the number to factor
Returns:
the list of prime factors of n

millerRabinPrimeTest

public static boolean millerRabinPrimeTest(int n)
Miller-Rabin probabilistic primality test for int type, used in such a way that a result is always guaranteed.

It uses the prime numbers as successive base therefore it is guaranteed to be always correct. (see Handbook of applied cryptography by Menezes, table 4.1)

Parameters:
n - number to test: an odd integer ≥ 3
Returns:
true if n is prime. false if n is definitely composite.


Copyright (c) 2003-2013 Apache Software Foundation