Package de.tilman_neumann.jml.factor

Class FactorAlgorithm

java.lang.Object

de.tilman_neumann.jml.factor.FactorAlgorithm

Direct Known Subclasses:

CFrac, CFrac63, CombinedFactorAlgorithm, EllipticCurveMethod, Hart_Fast, Hart_Fast2Mult, Hart_Simple, Hart_Squarefree, Hart_TDiv_Race, Hart_TDiv_Race2, HartLA63, Lehman_CustomKOrder, Lehman_Fast, Lehman_Simple, Lehman_Smith, PollardRho, PollardRho_ProductGcd, PollardRho31, PollardRhoBrent, PollardRhoBrent31, PollardRhoBrentMontgomery63, PollardRhoBrentMontgomery64, PollardRhoBrentMontgomeryR64Mul63, PSIQSBase, SIQS, SIQS_Small, SquFoF31, SquFoF31Preload, SquFoF63, TDiv, TDiv31, TDiv31Barrett, TDiv31Inverse, TDiv63, TDiv63Inverse, TinyEcm63, TinyEcm64, TinyEcm64_MontInline, TinyEcm64_MontSqr

public abstract class FactorAlgorithm
extends Object

Abstraction of integer factorization algorithms. This class provides a framework to find the complete prime factorization of N, requiring only to implement the method findSingleFactor(BigInteger).

Author:

Tilman Neumann

Field Summary

Fields

Modifier and Type	Field	Description
static FactorAlgorithm	DEFAULT	The best available single-threaded factor algorithm.
protected static int	NUM_PRIMES_FOR_31_BIT_TDIV	the number of primes needed to factor any int <= 2^31 - 1 using trial division
protected Integer	tdivLimit

Constructor Summary

Constructors

Constructor	Description
FactorAlgorithm()
FactorAlgorithm(Integer tdivLimit)

Method Summary

Modifier and Type	Method	Description
SortedMultiset<BigInteger>	factor(BigInteger N)	Decomposes the argument N into prime factors.
void	factor(BigInteger N, SortedMultiset<BigInteger> primeFactors)	Decomposes the argument N into prime factors.
abstract BigInteger	findSingleFactor(BigInteger N)	Find a single factor of the given N, which is composite and odd.
abstract String	getName()
void	searchFactors(FactorArguments args, FactorResult result)	Try to find at least one factor of the given args.N, which is composite and odd.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT

public static final FactorAlgorithm DEFAULT

The best available single-threaded factor algorithm. (multi-threading may not always be wanted)

NUM_PRIMES_FOR_31_BIT_TDIV

protected static final int NUM_PRIMES_FOR_31_BIT_TDIV

the number of primes needed to factor any int <= 2^31 - 1 using trial division

See Also:

Constant Field Values

tdivLimit

protected Integer tdivLimit

Constructor Detail

FactorAlgorithm

public FactorAlgorithm()

FactorAlgorithm

public FactorAlgorithm(Integer tdivLimit)

Method Detail

getName

public abstract String getName()

Returns:

The name of the algorithm, possibly including important parameters.

factor

public SortedMultiset<BigInteger> factor(BigInteger N)

Decomposes the argument N into prime factors. The result is a multiset of BigIntegers, sorted bottom-up.

Parameters:

N - Number to factor.

Returns:

The prime factorization of N

factor

public void factor(BigInteger N,
                   SortedMultiset<BigInteger> primeFactors)

Decomposes the argument N into prime factors.

Parameters:

N - Number to factor.

primeFactors - a map to which found factors are added

searchFactors

public void searchFactors(FactorArguments args,
                          FactorResult result)

Try to find at least one factor of the given args.N, which is composite and odd. This is a default implementation for algorithms that will only find a single factor or none at all. For sub-algorithms that may find more factors at once this method should be overwritten appropriately.

Parameters:

args -

result - the result of the factoring attempt. Should be initialized only once by the caller to reduce overhead.

findSingleFactor

public abstract BigInteger findSingleFactor(BigInteger N)

Find a single factor of the given N, which is composite and odd.

Parameters:

N -

Returns:

factor