Package org.apache.commons.math3.primes
Class SmallPrimes
- java.lang.Object
-
- org.apache.commons.math3.primes.SmallPrimes
-
class SmallPrimes extends java.lang.Object
Utility methods to work on primes within theint
range.- Since:
- 3.2
-
-
Field Summary
Fields Modifier and Type Field Description static int[]
PRIMES
The first 512 prime numbers.static int
PRIMES_LAST
The last number in PRIMES.
-
Constructor Summary
Constructors Modifier Constructor Description private
SmallPrimes()
Hide utility class.
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static int
boundedTrialDivision(int n, int maxFactor, java.util.List<java.lang.Integer> factors)
Extract factors in the rangePRIME_LAST+2
tomaxFactors
.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, java.util.List<java.lang.Integer> factors)
Extract small factors.static java.util.List<java.lang.Integer>
trialDivision(int n)
Factorization by trial division.
-
-
-
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.
-
-
Method Detail
-
smallTrialDivision
public static int smallTrialDivision(int n, java.util.List<java.lang.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, java.util.List<java.lang.Integer> factors)
Extract factors in the rangePRIME_LAST+2
tomaxFactors
.- Parameters:
n
- the number to factorize, must be >= PRIME_LAST+2 and must not contain any factor below PRIME_LAST+2maxFactor
- 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 java.util.List<java.lang.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.
-
-