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_Fast2Mult_FMA
,Hart_Fast2Mult2
,Hart_Simple
,Hart_Squarefree
,Hart_TDiv_Race
,Hart_TDiv_Race2
,Lehman_CustomKOrder
,Lehman_Fast
,Lehman_Simple
,Lehman_Smith
,PollardRho
,PollardRho_ProductGcd
,PollardRho31
,PollardRhoBrent
,PollardRhoBrent31
,PollardRhoBrentMontgomery64
,PollardRhoBrentMontgomery64_MH
,PollardRhoBrentMontgomery64_MHInlined
,PollardRhoBrentMontgomeryR64Mul63
,PSIQSBase
,SIQS
,SIQS_Small
,SquFoF31
,SquFoF31Preload
,SquFoF63
,TDiv
,TDiv31
,TDiv31Barrett
,TDiv31Inverse
,TDiv63
,TDiv63Inverse
,TinyEcm64
,TinyEcm64_MH
,TinyEcm64_MHInlined
public abstract class FactorAlgorithm
extends java.lang.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).
-
Field Summary
Fields Modifier and Type Field Description protected static int
NUM_PRIMES_FOR_31_BIT_TDIV
the number of primes needed to factor any int <= 2^31 - 1 using trial divisionprotected java.lang.Integer
tdivLimit
-
Constructor Summary
Constructors Constructor Description FactorAlgorithm()
FactorAlgorithm(java.lang.Integer tdivLimit)
-
Method Summary
Modifier and Type Method Description SortedMultiset<java.math.BigInteger>
factor(java.math.BigInteger N)
Decomposes the argument N into prime factors.void
factor(java.math.BigInteger N, SortedMultiset<java.math.BigInteger> primeFactors)
Decomposes the argument N into prime factors.abstract java.math.BigInteger
findSingleFactor(java.math.BigInteger N)
Find a single factor of the given N, which is composite and odd.static FactorAlgorithm
getDefault()
abstract java.lang.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 Details
-
NUM_PRIMES_FOR_31_BIT_TDIV
protected static final int NUM_PRIMES_FOR_31_BIT_TDIVthe number of primes needed to factor any int <= 2^31 - 1 using trial division- See Also:
- Constant Field Values
-
tdivLimit
protected java.lang.Integer tdivLimit
-
-
Constructor Details
-
FactorAlgorithm
public FactorAlgorithm() -
FactorAlgorithm
public FactorAlgorithm(java.lang.Integer tdivLimit)
-
-
Method Details
-
getDefault
- Returns:
- The best available single-threaded factor algorithm. (multi-threading may not always be wanted)
-
getName
public abstract java.lang.String getName()- Returns:
- The name of the algorithm, possibly including important parameters.
-
factor
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
Decomposes the argument N into prime factors.- Parameters:
N
- Number to factor.primeFactors
- a map to which found factors are added
-
searchFactors
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 java.math.BigInteger findSingleFactor(java.math.BigInteger N)Find a single factor of the given N, which is composite and odd.- Parameters:
N
- number to be factored.- Returns:
- factor
-