Package de.tilman_neumann.jml.factor
Class CombinedFactorAlgorithm
java.lang.Object
de.tilman_neumann.jml.factor.FactorAlgorithm
de.tilman_neumann.jml.factor.CombinedFactorAlgorithm
public class CombinedFactorAlgorithm extends FactorAlgorithm
Final combination of factor algorithms. Integrates trial division and ECM to search small factors of large numbers.
As such it is the best algorithm for general factoring arguments.
-
Field Summary
Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm
NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit
-
Constructor Summary
Constructors Constructor Description CombinedFactorAlgorithm(int numberOfThreads)
Simple constructor, computing the amount of trial division automatically and using PSIQS with sun.misc.Unsafe features.CombinedFactorAlgorithm(int numberOfThreads, java.lang.Integer tdivLimit, boolean permitUnsafeUsage)
Full constructor. -
Method Summary
Modifier and Type Method Description java.math.BigInteger
findSingleFactor(java.math.BigInteger N)
Find a single factor of the given N, which is composite and odd.java.lang.String
getName()
static void
main(java.lang.String[] args)
Run with command-line arguments or console input (if no command-line arguments are given).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 de.tilman_neumann.jml.factor.FactorAlgorithm
factor, factor, getDefault
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Constructor Details
-
CombinedFactorAlgorithm
public CombinedFactorAlgorithm(int numberOfThreads)Simple constructor, computing the amount of trial division automatically and using PSIQS with sun.misc.Unsafe features.- Parameters:
numberOfThreads
- the number of parallel threads for PSIQS
-
CombinedFactorAlgorithm
public CombinedFactorAlgorithm(int numberOfThreads, java.lang.Integer tdivLimit, boolean permitUnsafeUsage)Full constructor.- Parameters:
numberOfThreads
- the number of parallel threads for PSIQStdivLimit
- limit of primes p for trial division; if null then the value is determined by best experimental resultspermitUnsafeUsage
- if true then PSIQS_U using sun.misc.Unsafe features is used. This may be ~10% faster.
-
-
Method Details
-
getName
public java.lang.String getName()- Specified by:
getName
in classFactorAlgorithm
- Returns:
- The name of the algorithm, possibly including important parameters.
-
findSingleFactor
public java.math.BigInteger findSingleFactor(java.math.BigInteger N)Description copied from class:FactorAlgorithm
Find a single factor of the given N, which is composite and odd.- Specified by:
findSingleFactor
in classFactorAlgorithm
- Parameters:
N
- number to be factored.- Returns:
- factor
-
searchFactors
Description copied from class:FactorAlgorithm
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.- Overrides:
searchFactors
in classFactorAlgorithm
result
- the result of the factoring attempt. Should be initialized only once by the caller to reduce overhead.
-
main
public static void main(java.lang.String[] args)Run with command-line arguments or console input (if no command-line arguments are given). Usage for executable jar file: java -jar[[-t ] ] Some test numbers: 15841065490425479923 (64 bit) = 2604221509 * 6082841047 11111111111111111111111111 (84 bit) = {11=1, 53=1, 79=1, 859=1, 265371653=1, 1058313049=1} 5679148659138759837165981543 (93 bit) = {3=3, 466932157=1, 450469808245315337=1} 874186654300294020965320730991996026550891341278308 (170 bit) = {2=2, 3=1, 471997=1, 654743=1, 2855761=1, 79833227=1, 982552477=1, 1052328969055591=1} 11111111111111111111111111155555555555111111111111111 (173 bit) = {67=1, 157=1, 1056289676880987842105819104055096069503860738769=1} (only tdiv needed) 1388091470446411094380555803943760956023126025054082930201628998364642 (230 bit) = {2=1, 3=1, 1907=1, 1948073=1, 1239974331653=1, 50222487570895420624194712095309533522213376829=1} 10^71-1 = 99999999999999999999999999999999999999999999999999999999999999999999999 (236 bit) = {3=2, 241573142393627673576957439049=1, 45994811347886846310221728895223034301839=1} 10^79+5923 = 10000000000000000000000000000000000000000000000000000000000000000000000000005923 (263 bit) = {1333322076518899001350381760807974795003=1, 7500063320115780212377802894180923803641=1} 1794577685365897117833870712928656282041295031283603412289229185967719140138841093599 (280 bit) = 42181796536350966453737572957846241893933 * 42543889372264778301966140913837516662044603 2900608971182010301486951469292513060638582965350239259380273225053930627446289431038392125 (301 bit) = 33333 * 33335 * 33337 * 33339 * 33341 * 33343 * 33345 * 33347 * 33349 * 33351 * 33353 * 33355 * 33357 * 33359 * 33361 * 33363 * 33367 * 33369 * 33369 * 33371 = {3=11, 5=3, 7=6, 11=2, 13=2, 17=2, 19=1, 37=1, 41=1, 53=1, 59=1, 61=1, 73=1, 113=1, 151=1, 227=2, 271=1, 337=1, 433=1, 457=1, 547=1, 953=1, 11113=1, 11117=1, 11119=1, 33343=1, 33347=1, 33349=1, 33353=1, 33359=1} (only tdiv) - Parameters:
args
- [-t]
-