Class SmallPrimes

• public final class SmallPrimes
extends Object
Prime factorization of 32-bit integers. The code is taken from Apache Commons Math.
Since:
1.0
• Method Summary

Modifier and Type Method Description
static int boundedTrialDivision​(int n, int maxFactor, gnu.trove.list.array.TIntArrayList factors)
Extract factors in the range PRIME_LAST+2 to maxFactors.
static boolean isPrime​(int n)
Primality test: tells if the argument is a (provable) prime or not.
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 nextPrime​(int n)
Return the smallest prime greater than or equal to n.
static int[] primeFactors​(int n)
Prime factors decomposition.
static int smallTrialDivision​(int n, gnu.trove.list.array.TIntArrayList factors)
Extract small factors.
• Method Detail

• isPrime

public static boolean isPrime​(int n)
Primality test: tells if the argument is a (provable) prime or not.

It uses the Miller-Rabin probabilistic test in such a way that a result is guaranteed: it uses the firsts prime numbers as successive base (see Handbook of applied cryptography by Menezes, table 4.1).

Parameters:
n - number to test.
Returns:
true if n is prime. (All numbers < 2 return false).
• nextPrime

public static int nextPrime​(int n)
Return the smallest prime greater than or equal to n.
Parameters:
n - a positive number.
Returns:
the smallest prime greater than or equal to n.
Throws:
IllegalArgumentException - if n < 0.
• 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.
• smallTrialDivision

public static int smallTrialDivision​(int n,
gnu.trove.list.array.TIntArrayList 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,
gnu.trove.list.array.TIntArrayList 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.