Package org.apache.commons.math3.primes
Class SmallPrimes
java.lang.Object
org.apache.commons.math3.primes.SmallPrimes
Utility methods to work on primes within the
int
range.- Since:
- 3.2
-
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final int[]
The first 512 prime numbers.static final int
The last number in PRIMES. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic int
boundedTrialDivision
(int n, int maxFactor, List<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, List<Integer> factors) Extract small factors.trialDivision
(int n) Factorization by trial division.
-
Field Details
-
PRIMES
public static final int[] PRIMESThe 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_LASTThe last number in PRIMES.
-
-
Constructor Details
-
SmallPrimes
private SmallPrimes()Hide utility class.
-
-
Method Details
-
smallTrialDivision
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
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
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.
-