Class SmallPrimes
int
range.-
Field Summary
FieldsModifier and TypeFieldDescriptionA set of prime numbers mapped to an array of all integers between 0 (inclusive) and the least common multiple, i.e.(package private) static final int[]
The first 512 prime numbers.(package private) static final int
The last number inPRIMES
. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) static int
boundedTrialDivision
(int n, int maxFactor, List<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, List<Integer> factors) Extract small factors.trialDivision
(int n) Factorization by trial division.
-
Field Details
-
PRIMES
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
static final int PRIMES_LASTThe last number inPRIMES
. -
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.
-
-
Constructor Details
-
SmallPrimes
private SmallPrimes()Utility class.
-
-
Method Details
-
smallTrialDivision
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
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
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.
-