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

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

Methods inherited from class java.lang.Object

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

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 PSIQS

tdivLimit - limit of primes p for trial division; if null then the value is determined by best experimental results

permitUnsafeUsage - 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 class FactorAlgorithm

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 class FactorAlgorithm

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 class FactorAlgorithm

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 ]