|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.apache.commons.math3.primes.SmallPrimes
class SmallPrimes
Utility methods to work on primes within the int
range.
Field Summary | |
---|---|
static int[] |
PRIMES
The first 512 prime numbers. |
static int |
PRIMES_LAST
The last number in PRIMES. |
Constructor Summary | |
---|---|
private |
SmallPrimes()
Hide utility class. |
Method Summary | |
---|---|
static int |
boundedTrialDivision(int n,
int maxFactor,
List<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,
List<Integer> factors)
Extract small factors. |
static List<Integer> |
trialDivision(int n)
Factorization by trial division. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
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
Constructor Detail |
---|
private SmallPrimes()
Method Detail |
---|
public static int smallTrialDivision(int n, List<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, List<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 List<Integer> trialDivision(int n)
n
- the number to factor
public 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 ≥ 3
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |