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 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 Details

    • getName

      public java.lang.String getName()
      Specified by:
      getName in class FactorAlgorithm
      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 class FactorAlgorithm
      Parameters:
      N - number to be factored.
      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​(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 ]