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 and 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(BigInteger n) Strong primality test.
static boolean	isPrime(long n) Strong primality test.
static boolean	LucasPrimalityTest(BigInteger n, int k, org.apache.commons.math3.random.RandomGenerator rnd)
static BigInteger	nextPrime(BigInteger n) Return the smallest prime greater than or equal to n.
static long	nextPrime(long 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 List<BigInteger>	primeFactors(BigInteger num) Prime factors decomposition.
static long[]	primeFactors(long num) Prime factors decomposition.
static BigInteger	QuadraticSieve(BigInteger n, int bound)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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

QuadraticSieve

public static BigInteger QuadraticSieve(BigInteger n,
                                        int bound)

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