Class CFrac

java.lang.Object
de.tilman_neumann.jml.factor.FactorAlgorithm
de.tilman_neumann.jml.factor.cfrac.CFrac

public class CFrac
extends FactorAlgorithm
CFrac = Shanks' SQUFOF algorithm + carry along continuant recurrence + collect smooth relations + LinAlg solver.

The original CFrac was implemented by Morrison and Brillhart intending to factor the 7.th Fermat number F7 with 39 digits (~130 bits). Now this number can be factored single-threaded in a second or a few. Since 2017-09 Knuth-Schroeppel multipliers have been implemented, too. Stopping criterion for a single multiplier k: after complete period or at a maximum number of iterations. Switching multipliers seems to improve performance for small factor arguments (<60 bits) only; nonetheless we keep the code for possible further experiments.
  • Field Summary

    Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm

    NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit
  • Constructor Summary

    Constructors
    Constructor Description
    CFrac​(boolean use_all_i, int stopRoot, float stopMult, float C, float smoothBoundExponent, TDiv_CF auxFactorizer, MatrixSolver matrixSolver, int ks_adjust)
    Standard constructor.
  • Method Summary

    Modifier and Type Method Description
    java.math.BigInteger findSingleFactor​(java.math.BigInteger N)
    Test the current N.
    java.lang.String getName()  
    static void main​(java.lang.String[] args)
    Standalone test.
    protected java.math.BigInteger test()  

    Methods inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm

    factor, factor, getDefault, searchFactors

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • CFrac

      public CFrac​(boolean use_all_i, int stopRoot, float stopMult, float C, float smoothBoundExponent, TDiv_CF auxFactorizer, MatrixSolver matrixSolver, int ks_adjust)
      Standard constructor.
      Parameters:
      use_all_i -
      stopRoot - order of the root to compute the maximum number of iterations
      stopMult - multiplier to compute the maximum number of iterations
      C - multiplier for prime base size
      smoothBoundExponent -
      auxFactorizer - the algorithm to find smooth Q
      matrixSolver - matrix solver for the smooth congruence equation system
      ks_adjust -
  • 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)
      Test the current N.
      Specified by:
      findSingleFactor in class FactorAlgorithm
      Parameters:
      N - number to be factored.
      Returns:
      factor, or null if no factor was found.
    • test

      protected java.math.BigInteger test()
    • main

      public static void main​(java.lang.String[] args)
      Standalone test. Test numbers: F7 = 340282366920938463463374607431768211457
      Parameters:
      args - ignored