Top Description Fields Constructors Methods
org.apache.commons.math3.primes

pack-priv Class SmallPrimes

extends Object
Class Inheritance
Imports
java.math.BigInteger, java.util.ArrayList, .List, org.apache.commons.math3.util.FastMath
Utility methods to work on primes within the int range.
Since
3.2

Field Summary

Modifier and TypeField and Description
public static final int[]
PRIMES

The first 512 prime numbers.

public static final int
PRIMES_LAST

The last number in PRIMES.

Constructor Summary

AccessConstructor and Description
private
SmallPrimes()

Hide utility class.

Method Summary

Modifier and TypeMethod and Description
public static int

Returns:

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

Extract factors in the range PRIME_LAST+2 to maxFactors.

public static boolean

Returns:

true if n is prime. false if n is definitely composite.
millerRabinPrimeTest(final int
number to test: an odd integer ≥ 3
n)

Miller-Rabin probabilistic primality test for int type, used in such a way that a result is always guaranteed.

public static int

Returns:

the part of n which remains to be factored, it is either a prime or a semi-prime
smallTrialDivision(int
the number to factor, must be > 0.
n, final List<Integer>
the list where to add the factors.
factors)

Extract small factors.

public static List<Integer>

Returns:

the list of prime factors of n
trialDivision(int
the number to factor
n)

Factorization by trial division.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

PRIMESback to summary
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_LASTback to summary
public static final int PRIMES_LAST

The last number in PRIMES.

Constructor Detail

SmallPrimesback to summary
private SmallPrimes()

Hide utility class.

Method Detail

boundedTrialDivisionback to summary
public static int boundedTrialDivision(int n, int maxFactor, List<Integer> factors)

Extract factors in the range PRIME_LAST+2 to maxFactors.

Parameters
n:int

the number to factorize, must be >= PRIME_LAST+2 and must not contain any factor below PRIME_LAST+2

maxFactor:int

the upper bound of trial division: if it is reached, the method gives up and returns n.

factors:List<Integer>

the list where to add the factors.

Returns:int

n or 1 if factorization is completed.

millerRabinPrimeTestback to summary
public static boolean millerRabinPrimeTest(final 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:int

number to test: an odd integer ≥ 3

Returns:boolean

true if n is prime. false if n is definitely composite.

smallTrialDivisionback to summary
public static int smallTrialDivision(int n, final List<Integer> factors)

Extract small factors.

Parameters
n:int

the number to factor, must be > 0.

factors:List<Integer>

the list where to add the factors.

Returns:int

the part of n which remains to be factored, it is either a prime or a semi-prime

trialDivisionback to summary
public static List<Integer> trialDivision(int n)

Factorization by trial division.

Parameters
n:int

the number to factor

Returns:List<Integer>

the list of prime factors of n