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.- Author:
- Tilman Neumann
-
-
Field Summary
-
Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm
DEFAULT, 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, Integer tdivLimit, boolean permitUnsafeUsage)
Full constructor.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description BigInteger
findSingleFactor(BigInteger N)
Find a single factor of the given N, which is composite and odd.String
getName()
static void
main(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
-
-
-
-
Constructor Detail
-
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, 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 Detail
-
getName
public String getName()
- Specified by:
getName
in classFactorAlgorithm
- Returns:
- The name of the algorithm, possibly including important parameters.
-
findSingleFactor
public BigInteger findSingleFactor(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
- Returns:
- factor
-
searchFactors
public void searchFactors(FactorArguments args, FactorResult result)
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(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 in 211ms. (done by PSIQS) 11111111111111111111111111 (84 bit) = {11=1, 53=1, 79=1, 859=1, 265371653=1, 1058313049=1} in 185ms. (tdiv + PSIQS) 5679148659138759837165981543 (93 bit) = {3=3, 466932157=1, 450469808245315337=1} in 194ms. (tdiv + PSIQS) 874186654300294020965320730991996026550891341278308 (170 bits) = {2=2, 3=1, 471997=1, 654743=1, 2855761=1, 79833227=1, 982552477=1, 1052328969055591=1} in 685ms (tdiv + ECM + PSIQS) 11111111111111111111111111155555555555111111111111111 (173 bit) = {67=1, 157=1, 1056289676880987842105819104055096069503860738769=1} in 21ms. (only tdiv needed) 1388091470446411094380555803943760956023126025054082930201628998364642 (230 bit) = {2=1, 3=1, 1907=1, 1948073=1, 1239974331653=1, 50222487570895420624194712095309533522213376829=1} in 304ms. (tdiv + ECM + PSIQS) 10^71-1 = 99999999999999999999999999999999999999999999999999999999999999999999999 (236 bits) = {3=2, 241573142393627673576957439049=1, 45994811347886846310221728895223034301839=1} in 14s, 471ms. (tdiv + PSIQS) 10^79+5923 = 10000000000000000000000000000000000000000000000000000000000000000000000000005923 (263 bit) = {1333322076518899001350381760807974795003=1, 7500063320115780212377802894180923803641=1} in 1m, 35s, 243ms. (PSIQS) 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} in 10ms. (only tdiv) - Parameters:
args
- [-t]
-
-