Package cc.redberry.rings.primes
Class BigPrimes
java.lang.Object
cc.redberry.rings.primes.BigPrimes
public final class BigPrimes extends Object
Prime factorization of BigIntegers
- Since:
- 1.0
-
Method Summary
Modifier and Type Method Description static BigInteger
fermat(BigInteger n, long upperBound)
Fermat's factoring algorithm works like trial division, but walks in the opposite direction.static boolean
isPrime(long n)
Strong primality test.static boolean
isPrime(BigInteger n)
Strong primality test.static boolean
LucasPrimalityTest(BigInteger n, int k, org.apache.commons.math3.random.RandomGenerator rnd)
static long
nextPrime(long n)
Return the smallest prime greater than or equal to n.static BigInteger
nextPrime(BigInteger n)
Return the smallest prime greater than or equal to n.static BigInteger
PollardP1(BigInteger n, long upperBound)
Pollards's p-1 algorithm.static BigInteger
PollardRho(BigInteger n, int attempts, org.apache.commons.math3.random.RandomGenerator rn)
Pollards's rho algorithm (random search version).static BigInteger
PollardRho(BigInteger n, long upperBound)
Pollards's rho algorithm.static long[]
primeFactors(long num)
Prime factors decomposition.static List<BigInteger>
primeFactors(BigInteger num)
Prime factors decomposition.static BigInteger
QuadraticSieve(BigInteger n, int bound)
-
Method Details
-
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
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
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
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 factorupperBound
- 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 factorattempts
- number of random attempts- Returns:
- a single factor of
n
or null if no factors found
-
PollardRho
Pollards's rho algorithm.- Parameters:
n
- integer to factorupperBound
- expected B-smoothness- Returns:
- a single factor of
n
or null if no factors found
-
PollardP1
Pollards's p-1 algorithm.- Parameters:
n
- integer to factorupperBound
- expected B-smoothness- Returns:
- a single factor of
n
or null if no factors found
-
QuadraticSieve
-
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
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
-