Class BigPrimes

• public final class BigPrimes
extends Object
Prime factorization of BigIntegers
Since:
1.0
• Method Detail

• isPrime

public static boolean isPrime​(long n)
Strong primality test. Switches between trial divisions, probabilistic Miller-Rabin (ensures that is not prime), probabilistic Lucas test (ensures that is prime) and finally (if all above fail to provide deterministic answer) to Pollard's p-1, Pollard's rho and quadratic sieve.
Parameters:
n - number to test
Returns:
true if input is certainly prime, false is certainly composite
• isPrime

public static boolean isPrime​(BigInteger n)
Strong primality test. Switches between trial divisions, probabilistic Miller-Rabin (ensures that is not prime), probabilistic Lucas test (ensures that is prime) and finally (if all above fail to provide deterministic answer) to Pollard's p-1, Pollard's rho and quadratic sieve.
Parameters:
n - number to test
Returns:
true if input is certainly prime, false is certainly composite
• LucasPrimalityTest

public static boolean LucasPrimalityTest​(BigInteger n,
int k,
org.apache.commons.math3.random.RandomGenerator rnd)
• nextPrime

public static BigInteger nextPrime​(BigInteger n)
Return the smallest prime greater than or equal to n.
Parameters:
n - a positive number.
Returns:
the smallest prime greater than or equal to n.
Throws:
IllegalArgumentException - if n < 0.
• nextPrime

public static long nextPrime​(long n)
Return the smallest prime greater than or equal to n.
Parameters:
n - a positive number.
Returns:
the smallest prime greater than or equal to n.
Throws:
IllegalArgumentException - if n < 0.
• fermat

public static BigInteger fermat​(BigInteger n,
long upperBound)
Fermat's factoring algorithm works like trial division, but walks in the opposite direction. Thus, it can be used to factor a number that we know has a factor in the interval [Sqrt(n) - upperBound, Sqrt(n) + upperBound].
Parameters:
n - number to factor
upperBound - upper bound
Returns:
a single factor
• PollardRho

public static BigInteger PollardRho​(BigInteger n,
int attempts,
org.apache.commons.math3.random.RandomGenerator rn)
Pollards's rho algorithm (random search version).
Parameters:
n - integer to factor
attempts - number of random attempts
Returns:
a single factor of n or null if no factors found
• PollardRho

public static BigInteger PollardRho​(BigInteger n,
long upperBound)
Pollards's rho algorithm.
Parameters:
n - integer to factor
upperBound - expected B-smoothness
Returns:
a single factor of n or null if no factors found
• PollardP1

public static BigInteger PollardP1​(BigInteger n,
long upperBound)
Pollards's p-1 algorithm.
Parameters:
n - integer to factor
upperBound - expected B-smoothness
Returns:
a single factor of n or null if no factors found
• primeFactors

public static long[] primeFactors​(long num)
Prime factors decomposition. The algorithm switches between trial divisions, Pollard's p-1, Pollard's rho and quadratic sieve.
Parameters:
num - number to factorize
Returns:
list of prime factors of n
Throws:
IllegalArgumentException - if n is negative
• primeFactors

public static List<BigInteger> primeFactors​(BigInteger num)
Prime factors decomposition. The algorithm switches between trial divisions, Pollard's p-1, Pollard's rho and quadratic sieve.
Parameters:
num - number to factorize
Returns:
list of prime factors of n
Throws:
IllegalArgumentException - if n is negative