class SmallPrimes
extends java.lang.Object
int
range.Modifier and Type | Field and Description |
---|---|
static int[] |
PRIMES
The first 512 prime numbers.
|
static int |
PRIMES_LAST
The last number in PRIMES.
|
Modifier | Constructor and Description |
---|---|
private |
SmallPrimes()
Hide utility class.
|
Modifier and Type | Method and Description |
---|---|
static int |
boundedTrialDivision(int n,
int maxFactor,
java.util.List<java.lang.Integer> factors)
Extract factors in the range
PRIME_LAST+2 to maxFactors . |
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.
|
public static final int[] PRIMES
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.
public static final int PRIMES_LAST
public static int smallTrialDivision(int n, java.util.List<java.lang.Integer> factors)
n
- the number to factor, must be > 0.factors
- the list where to add the factors.public static int boundedTrialDivision(int n, int maxFactor, java.util.List<java.lang.Integer> factors)
PRIME_LAST+2
to maxFactors
.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.public static java.util.List<java.lang.Integer> trialDivision(int n)
n
- the number to factorpublic static boolean millerRabinPrimeTest(int n)
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)
n
- number to test: an odd integer ≥ 3Copyright (c) 2003-2013 Apache Software Foundation