Class 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
    • 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.
      • 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 ]