Class SmallPrimes
- java.lang.Object
-
- org.apache.commons.numbers.primes.SmallPrimes
-
final class SmallPrimes extends java.lang.Object
Utility methods to work on primes within theint
range.
-
-
Field Summary
Fields Modifier and Type Field Description (package private) static java.util.Map.Entry<java.util.Set<java.lang.Integer>,int[]>
PRIME_NUMBERS_AND_COPRIME_EQUIVALENCE_CLASSES
A set of prime numbers mapped to an array of all integers between 0 (inclusive) and the least common multiple, i.e.(package private) static int[]
PRIMES
The first 512 prime numbers.(package private) static int
PRIMES_LAST
The last number inPRIMES
.
-
Constructor Summary
Constructors Modifier Constructor Description private
SmallPrimes()
Utility class.
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description (package private) static int
boundedTrialDivision(int n, int maxFactor, java.util.List<java.lang.Integer> factors)
Extract factors betweenPRIME_LAST + 2
andmaxFactors
.(package private) static boolean
millerRabinPrimeTest(int n)
Miller-Rabin probabilistic primality test for int type, used in such a way that a result is always guaranteed.(package private) static int
smallTrialDivision(int n, java.util.List<java.lang.Integer> factors)
Extract small factors.(package private) static java.util.List<java.lang.Integer>
trialDivision(int n)
Factorization by trial division.
-
-
-
Field Detail
-
PRIMES
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
static final int PRIMES_LAST
The last number inPRIMES
.
-
PRIME_NUMBERS_AND_COPRIME_EQUIVALENCE_CLASSES
static final java.util.Map.Entry<java.util.Set<java.lang.Integer>,int[]> PRIME_NUMBERS_AND_COPRIME_EQUIVALENCE_CLASSES
A set of prime numbers mapped to an array of all integers between 0 (inclusive) and the least common multiple, i.e. the product, of those prime numbers (exclusive) that are not divisible by any of these prime numbers. The prime numbers in the set are among the first 512 prime numbers, and theint
array containing the numbers undivisible by these prime numbers is sorted in ascending order.The purpose of this field is to speed up trial division by skipping multiples of individual prime numbers, specifically those contained in the key of this
Entry
, by only trying integers that are equivalent to one of the integers contained in the value of thisEntry
modulo the least common multiple of the prime numbers in the set.Note that, if
product
is the product of the prime numbers, the last number in the array of coprime integers is necessarilyproduct - 1
, because ifproduct ≡ 0 mod p
, thenproduct - 1 ≡ -1 mod p
, and0 ≢ -1 mod p
for any prime number p.
-
-
Method Detail
-
smallTrialDivision
static int smallTrialDivision(int n, java.util.List<java.lang.Integer> factors)
Extract small factors.- Parameters:
n
- Number to factor, must be > 0.factors
- 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
static int boundedTrialDivision(int n, int maxFactor, java.util.List<java.lang.Integer> factors)
Extract factors betweenPRIME_LAST + 2
andmaxFactors
.- Parameters:
n
- Number to factorize, must be larger thanPRIME_LAST + 2
and must not contain any factor belowPRIME_LAST + 2
.maxFactor
- Upper bound of trial division: if it is reached, the method gives up and returnsn
.factors
- the list where to add the factors.- Returns:
n
(or 1 if factorization is completed).
-
trialDivision
static java.util.List<java.lang.Integer> trialDivision(int n)
Factorization by trial division.- Parameters:
n
- Number to factor.- Returns:
- the list of prime factors of
n
.
-
millerRabinPrimeTest
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 it is definitely composite.
-
-